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;
执行如下程序：
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);
}
}