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

2023-08-01 09:39:04

GCD SUM

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

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 5

1 3

Sample Output

19 55 55

3 3 6

 #include <iostream>

 #include <stdio.h>

 #include <string.h>

 using namespace std;

 #define MAX 100010

 #define ll long long

 ll mu[MAX]= {},mb[MAX]= {};

 void init()

 {

     int i,j;

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

     {

         if(!mu[i])

         {

             mu[i]=i;

             if(i>)continue;

             j=i*i;

             while(j<MAX)

             {

                 mu[j]=i;

                 j+=i;

             }

         }

     }

     mu[]=;

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

     {

         if((i/mu[i])%mu[i]==)mu[i]=;

         else mu[i]=-mu[i/mu[i]];

     }

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

     mb[i]=mu[i]*i,mu[i]+=mu[i-],mb[i]+=mb[i-];

 }

 void solve(int n,int m)

 {

     ll ans,ansx,ansy,x,y;

     ans=ansx=ansy=;

     int i,j,k;

     for(i=(n>m?m:n);i>;)

     {

         x=n/i,y=m/i;

         k=max(n/(x+),m/(y+));

         ans+=x*y*(mu[i]-mu[k]);

         ansx+=(mb[i]-mb[k])*y*(+x)*x/;

         ansy+=(mb[i]-mb[k])*x*(+y)*y/;

         i=k;

     }

     printf("%lld %lld %lld\n",ans,ansx,ansy);

 }

 int main()

 {

     init();

     int n,m;

     while(scanf("%d%d",&n,&m)!=EOF)

     {

         solve(n,m);

     }

 }