hdu3501-阿里云开发者社区

hdu3501

2015-05-10 1342

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Problem Description

Given a positive integer N, your task is to calculate the sum of the positive integers less than N which are not coprime to N. A is said to be coprime to B if A, B share no common positive divisors except 1.

Input

For each test case, there is a line containing a positive integer N(1 ≤ N ≤ 1000000000). A line containing a single 0 follows the last test case.

Output

For each test case, you should print the sum module 1000000007 in a line.

Sample Input

  3 4 0
 

Sample Output

0 2

  代码如下：
 

#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
int phi(long long m)
{
    long long rea=m;
    for(long long i=2;i*i<=m;i++)
     {
         if(m%i==0)
         rea-=rea/i;
         while(m%i==0)
         m/=i;
     }
     if(m>1)
        rea-=rea/m;
     return rea;
}
int main()
{
    /*欧拉函数一个小小的性质：
    求小于n并且与n互质的数的和为：m*phi[m]/2；*/
    long long m,ans;
    while(~scanf("%lld",&m))
     {
         if(m==0)break;
         ans=phi(m);
         ans=(m*(m-1)/2-m*ans/2)%mod;
         printf("%lld\n",ans);
     }
    return 0;
}#include <iostream>
#include <cstdio>
using namespace std;
const int mod=1000000007;
int phi(long long m)
{
long long rea=m;
for(long long i=2;i*i<=m;i++)
{
if(m%i==0)
rea-=rea/i;
while(m%i==0)
m/=i;
}
if(m>1)
rea-=rea/m;
return rea;
}
int main()
{
/*欧拉函数一个小小的性质：
求小于n并且与n互质的数的和为：n*phi[n]/2；*/
long long m,ans;
while(~scanf("%lld",&m))
{
if(m==0)break;
ans=phi(m);
ans=(m*(m-1)/2-m*ans/2)%mod;
printf("%lld\n",ans);
}
return 0;
}

hdu3501

热门文章

最新文章

相关电子书