Calculation 2 HDU

不会做啊。。。记一下做法

做法是计算小于n且与n互质的数的和；根据如果gcd(i,n)==1，那么gcd(n-i,n)==1，对这些数两两一组分组，使得每组的和为n

后面自己去想了一下，想出了一个奇怪的做法。。

化简出来小于n且与n互质的数的和是$\sum_{d|n}\mu(d)\sum_{j=1}^{{\lfloor}\frac{n-1}{d}{\rfloor}}(dj)$

于是暴力枚举因子，暴力根号n求莫比乌斯函数，得到一个O(n)做法。。。

过了。。。

 #include<cstdio>

 #include<algorithm>

 #include<cstring>

 #include<vector>

 using namespace std;

 #define fi first

 #define se second

 #define mp make_pair

 #define pb push_back

 typedef long long ll;

 typedef unsigned long long ull;

 typedef pair<int,int> pii;

 #define md 1000000007

 #define N 100000

 ll n,ans;

 ll F(ll k)

 {

     //if(n%k!=0)    return 0;

     ll ed=(n-)/k;

     return (k+ed*k)%md*ed%md*%md;

 }

 ll prime[],len;

 bool nprime[];

 ll gmu(ll x)

 {

     //if(x==1)    return 1;

     int i,ans=,ed=floor(sqrt(x+0.5));

     bool fl;

     for(i=;prime[i]<=ed;i++)

     {

         fl=;

         //printf("a%lld %lld\n",i,x);

         while(x%prime[i]==)

         {

             if(fl)    return ;

             fl=;

             x/=prime[i];

             ans*=(-);

         }

     }

     if(x!=)    ans*=(-);

     return ans;

 }

 int main()

 {

     ll i,j;

     for(i=;i<=N;i++)

     {

         if(!nprime[i])    prime[++len]=i;

         for(j=;j<=len&&i*prime[j]<=N;j++)

         {

             nprime[i*prime[j]]=;

             if(i%prime[j]==)    break;

         }

     }

     //n=4;

     //while(1)

     //{scanf("%lld",&i);printf("%lld\n",gmu(i));}

     while()

     {

         scanf("%lld",&n);

         if(n==)    break;

         ll sq=sqrt(n+0.5);

         if(sq*sq==n)    sq--;

         ans=;

         for(i=;i<=sq;i++)

         {

             if(n%i!=)    continue;

             ans=(ans+gmu(i)*F(i)+md)%md;

             ans=(ans+gmu(n/i)*F(n/i)+md)%md;

         }

         sq++;

         if(sq*sq==n)    ans=(ans+gmu(sq)*F(sq)+md)%md;

         printf("%lld\n",(n*(n-)%md*%md-ans+md)%md);

         //printf("%lld\n",ans);

     }

     return ;

 }

巴特西

Calculation 2 HDU - 3501

最新文章

热门文章