首页 > 代码库 > GCD SUM 强大的数论，容斥定理

GCD SUM 强大的数论，容斥定理

2024-07-12 19:55:20   214人阅读

GCD SUM

Time Limit: 8000/4000MS (Java/Others) Memory Limit: 128000/64000KB (Java/Others)
SubmitStatus

Problem Description

给出N,M
执行如下程序：
long long  ans = 0,ansx = 0,ansy = 0;
for(int i = 1; i <= N; i ++)
   for(int j = 1; j <= M; j ++)
       if(gcd(i,j) == 1) ans ++,ansx += i,ansy += j;
cout << ans << " " << ansx << " " << ansy << endl;

Input

多组数据，每行两个数N,M(1 <= N,M <= 100000)。

 

Output

如题所描述，每行输出3个数，ans,ansx,ansy，空格隔开

Sample Input

5 51 3

Sample Output

19 55 553 3 6

 1 #include <iostream> 2 #include <stdio.h> 3 #include <string.h> 4 using namespace std; 5 #define MAX 100010 6 #define ll long long 7 ll mu[MAX]= {0},mb[MAX]= {0}; 8 void init() 9 {10     int i,j;11     for(i=2; i<MAX; i++)12     {13         if(!mu[i])14         {15             mu[i]=i;16             if(i>1000)continue;17             j=i*i;18             while(j<MAX)19             {20                 mu[j]=i;21                 j+=i;22             }23         }24     }25     mu[1]=1;26     for(i=2; i<MAX; i++)27     {28         if((i/mu[i])%mu[i]==0)mu[i]=0;29         else mu[i]=-mu[i/mu[i]];30     }31     for(i=1; i<MAX; i++)32     mb[i]=mu[i]*i,mu[i]+=mu[i-1],mb[i]+=mb[i-1];33 }34 void solve(int n,int m)35 {36     ll ans,ansx,ansy,x,y;37     ans=ansx=ansy=0;38     int i,j,k;39     for(i=(n>m?m:n);i>0;)40     {41         x=n/i,y=m/i;42         k=max(n/(x+1),m/(y+1));43         ans+=x*y*(mu[i]-mu[k]);44         ansx+=(mb[i]-mb[k])*y*(1+x)*x/2;45         ansy+=(mb[i]-mb[k])*x*(1+y)*y/2;46         i=k;47     }48     printf("%lld %lld %lld\n",ans,ansx,ansy);49 }50 int main()51 {52     init();53     int n,m;54     while(scanf("%d%d",&n,&m)!=EOF)55     {56         solve(n,m);57     }58 }
View Code

 


联系
我们