GCD - Extreme (II) UVA - 11426 欧拉函数与gcd

题目大意：累加从1到n，任意两个数的gcd(i,j)(1=<i<n&&i<j<=n)。

题解：假设a<b，如果gcd(a,b)=c。则gcd(a/c,b/c)=1。也就是说a/c和b/c互质，而与a/c互质的数一共有oula(a/c)个，也就是说这里的b/c一共有oula(a/c)种选择，同理，gcd(a,b)=c,a的选择就会有,oula(b/c)种。

所以 gcd(x,y)=1 ,枚举每一个x，然后在枚举x的k倍，答案就是ans[x*k]+=oula(x)*k。最后再求一下去前缀和就行了。

code：

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll maxn=+;

const ll N=+;

ll sum[N];

ll ans[N];

ll p[N];

void oula(){

    ll i,j;

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

        p[i]=i;

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

        p[i]/=;

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

    if(p[i]==i)

    {

        for(j=i; j<=maxn; j+=i)

            p[j]=(p[j]/i*(i-));

    }

}

void solve(){

    for(ll x=;x<maxn;x++)

        for(ll i=;i*x<maxn;i++)

            ans[i*x]=ans[i*x]+p[x]*i;

    for(ll i=;i<maxn;i++) ans[i]+=ans[i-];

}

int main(){

    oula();

    ll n;

    solve();

    while(cin>>n,n) cout<<ans[n]<<endl;

    return ;

}

巴特西

GCD - Extreme (II) UVA - 11426 欧拉函数与gcd

最新文章

热门文章