T1:bzoj2705

题目描述：

给定一个n求\(\sum\limits_{i=1}^ngcd(i,n)\)

因为n太大，所以O(n)的做法肯定不行，然后就去想根号的方法。

\[\sum\limits_{i=1}^{n}gcd(i,n)\]\[=\sum\limits_{k|n}k*\sum\limits_{i=1}^n[gcd(i,n)==k]\]\[=\sum\limits_{k|n}k*\sum\limits_{i=1}^n[gcd(\frac{i}{k},\frac{n}{k})==1]\]\[=\sum\limits_{k|n}k*\sum_{i=1}^{\frac{n}{k}}[gcd(i,\frac{n}{k})==1]\]\[=\sum_{k|n}{k*φ(\frac{n}{k})}\]

然后i从1到\(\sqrt{n}\)去枚举n的因数，然后将i*φ(n/i)与n/i与φ(i)全部计入答案，就可以做到\(\sqrt{n}*\sqrt{n}\)的复杂度，因为第二个根号是求欧拉函数的复杂度，所以实际的复杂度没有这么高

代码：

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
ll phi(ll x)
{
    ll ans=1;
    for(ll i=2;i*i<=x;++i)
    {
        if(x%i==0)
        {
            ans*=(i-1);
            x/=i;
        }
        while(x%i==0)
        {
            ans*=i;
            x/=i;
        }
    }
    if(x!=1)
    ans*=(x-1);
    return ans;
}
int main()
{
    ios::sync_with_stdio(false);
    ll n;
    cin>>n;
    ll ans=0;
    ll i;
    for(i=1;i*i<=n;++i)
        if(n%i==0)
            ans+=i*phi(n/i)+(n/i)*phi(i);
    if(i*i==n) ans-=i*phi(i);
    cout<<ans;
    return 0;
}

T2:exbzoj2705：

没有评测,

题目描述：

给定一个整数n(1<=n<=100000)，你需要求出\(\sum\limits_{i=1}^n\sum\limits_{j=1}^igcd(i,j)\)

暴力做法：将上个题中的n循环起来，最后记录每个循环所求的和。明显TLE

正解:

\[\sum\limits_{i=1}^n\sum\limits_{j=1}^igcd(i,j)\]

枚举因数k

\[\sum\limits_{k=1}^nk*\sum\limits_{i=1}^n\sum\limits_{j=1}^i[gcd(i,j)==k]\]

考虑所有最大公因数为k的情况，设\(i=ak,j=bk(a>=b)\)若要i与j做大公约数为k，则必须满足gcd(a,b)=1，满足此条件的所有情况数为φ(b)，然后考虑b的取值范围，因为必须满足b*k<=n，所以\(b<=[\frac{n}{k}]\)。所以答案为\[\sum\limits_{k=1}^nk*\sum\limits_{i=1}^{\frac{n}{k}}φ(i)\]所以线性求出欧拉函数，并求出前缀和即可。

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=100000+100;
int phi[N],phi_sum[N];
void getphi()
{
    for(int i=1;i<N;++i)
        phi[i]=i;
    phi[1]=1;
    for(int i=2;i<N;++i)
        if(phi[i]==i)
            for(int j=i;j<=N;j+=i)
                phi[j]=phi[j]/i*(i-1);
    for(int i=1;i<N;++i)
        phi_sum[i]=phi_sum[i-1]+phi[i];
}
int n;
int main()
{
    getphi();
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
        long long ans=0;
        for(int i=1;i<=n;++i)
            ans+=phi_sum[n/i]*i;
        cout<<ans<<endl;
    }
    return 0;
}

T3:uva11417

别问我为什么是luogu

题目描述：

给定一个整数n(1<=n<=100000)，求\(\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^ngcd(i,j)\)

解法：

\[\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^ngcd(i,j)\]

枚举因数k

\[\sum\limits_{k=1}^nk*\sum\limits_{i=1}^{n-1}\sum\limits_{j=i+1}^n[gcd(i,j)==k]\]

考虑所有最大公因数为k的情况，设\(i=ak,j=bk(b>a)\)若要i与j做大公约数为k，则必须满足gcd(a,b)=1，满足此条件的所有情况数为φ(b)，然后考虑b的取值范围，因为必须满足b*k<=n，所以\(b<=[\frac{n}{k}]\)。所以答案为\[\sum\limits_{k=1}^nk*\sum\limits_{i=1}^{\frac{n}{k}}φ(i)\]所以线性求出欧拉函数，并求出前缀和即可。

为什么和上面一样

但是因为i和j都不能为0并且j>i即b>a，所以b不能为1，所以要在最后减去φ(1)的情况，也就相当于把里面的i从2开始枚举。

所以最终答案为\[\sum\limits_{k=1}^nk*\sum\limits_{i=1}^{\frac{n}{k}}φ(i)-1\]

代码：

#include<cstdio>
#include<iostream>
using namespace std;
const int N=100000+100;
int phi[N],phi_sum[N];
void getphi()
{
    for(int i=1;i<N;++i)
        phi[i]=i;
    phi[1]=1;
    for(int i=2;i<N;++i)
        if(phi[i]==i)
            for(int j=i;j<=N;j+=i)
                phi[j]=phi[j]/i*(i-1);
    for(int i=1;i<N;++i)
        phi_sum[i]=phi_sum[i-1]+phi[i];
}
int n;
int main()
{
    getphi();
    while(1)
    {
        scanf("%d",&n);
        if(!n) break;
        long long ans=0;
        for(int i=1;i<=n;++i)
            ans+=(phi_sum[n/i]-1)*i;
        cout<<ans<<endl;
    }
    return 0;
}

T4:luogu2398

题目描述:

给定一个n(1<=n<=100000),求\(\sum\limits_{i=1}^n\sum\limits_{j=1}^ngcd(i,j)\)

解法:

发现这个题数上面两个题的综合，所以，嘿嘿，将上面的两个题答案加起来即可，所以最终答案为\[\sum\limits_{k=1}^n2*k*\sum\limits_{i=1}^{\frac{n}{k}}φ(i)-1\]

代码:

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
const int N=100000+100;
ll ans,phi[N],phi_sum[N],n;
void getphi()
{
    for(int i=1;i<N;++i)
        phi[i]=i;
    phi[1]=1;
    for(int i=2;i<N;++i)
        if(phi[i]==i)
            for(int j=i;j<=N;j+=i)
                phi[j]=phi[j]/i*(i-1);
    for(int i=1;i<N;++i)
        phi_sum[i]=phi_sum[i-1]+phi[i];
}
int main()
{
    cin>>n;
    getphi();
    for(int i=1;i<=n;++i)
        ans+=(phi_sum[n/i]*2-1)*i;
    cout<<ans;
    return 0;
}