【bzoj2190】[SDOI2008]仪仗队

2015.05.27 20:40 Wed | 17次阅读 | 旧日oi | 固定链接 | 源码

题目大意,给定n,求gcd(i,j)==1(i<=n,j<=n) 的(i,j)对数。
题解
题目大意已经说完了……快筛欧拉函数,求一下前缀和就好了。

我的程序

#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#define ll long long
using namespace std;
ll n,ans;
ll phi[50005],prime[50005],cnt;
bool vis[50005];
void quick_eular(ll x)
{
    phi[1]=1;
    for(ll i=2;i<=x;i++)
    {
        if(!vis[i]) prime[++cnt]=i,phi[i]=i-1;
        for(int j=1;j<=cnt&&prime[j]*i<=x;j++)
        {
            vis[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    cin>>n;n--;
    quick_eular(n);
    for(int i=1;i<=n;i++) ans+=phi[i];
    cout<<ans*2+1<<endl;
}```