很容易想到从1到 n\sqrt{n}n 枚举因子,由于每一个小于根号 n\sqrt{n}n 的因子必定有另一个较大的因子与其对应,所以每找到一个小于 n\sqrt{n}n 的因子,答案就+2。
但完全平方数是个个例,拿9举例:当我们枚举到3时,它对应的因子也是3,这样就会重复。所以我们需要特判。
部分代码:
for(ll i=1;i*i<=n;i++) // 从1枚举到根号n if(n%i==0) if(i*i==n) // 如果i等于根号n ans++; // 答案就只+1 else ans+=2; // 否则答案+2 printf("%lld",ans);
注册一个 核OJ_核桃编程 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 核OJ_核桃编程 通用账户