题目链接:
分析:
我们可以枚举x的约束为xi,那么结果就等于
sum = sigma( xi * mi) mi表示的是与x最大公约数
为xi的数的个数,那么我们的问题就转化成了求mi;
如果GCD(x,m) == f那么我们将其转化到 [1,x/f]区间内
则与x/f互质的数的个数转化到[1,x]区间内就等于最大
公约数为f的数的个数。
代码如下:
#include <iostream>#include <cstdio>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;LL phi(LL n){LL rea = n;for(LL i = 2;i*i<=n;i++){if(n%i==0){rea = rea – rea/i;while(n%i==0) n/=i;}}if(n>1) rea = rea – rea/n;return rea;}int main(){LL n;while(~scanf("%lld",&n)){LL ans = 0;for(LL i=1;i*i<=n;i++){if(n%i==0&&i*i==n)ans+=phi(i)*i;if(n%i==0&&i*i!=n){ans+=phi(n/i)*i;ans+=phi(i)*n/i;}}printf("%lld\n",ans);}return 0;}
,如果心胸不似海,又怎能有海一样的事业。