JDOJ-2258&&2259

Description

2258：就是求长与n互质的数的个数。
2259：求长宽互质的对数。

2258:直接求
2259:求

2258:

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LL long long
using namespace std;
LL n,m;
int cnt,top;
int z[101000];
bool v[101000];
int prime[101000];
void quick_prime()
{
    for(int i=2;i<=100000;i++)
    {
        if(!v[i]) prime[++cnt]=i;
        for(int j=1;j<=cnt&&prime[j]*i<=100000;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}
int main()
{
    quick_prime();
    while(scanf("%lld",&n)!=EOF)
    {
        if(n==1||n==0)
        {
            printf("%d\n",n<<1);
            continue;
        }
        m=n;
        top=0;
        for(int i=1;i<=cnt&&prime[i]<=n;i++)
            if(n%prime[i]==0)
            {
                z[++top]=prime[i];
                while(n%prime[i]==0)
                    n/=prime[i];
            }
        if(n!=1)
            z[++top]=n;
        for(int i=1;i<=top;i++)
            m=m/z[i]*(z[i]-1);
        printf("%lld\n",m);
    }
    return 0;
}

2259:

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <cstring>
#define N 1000001
#define LL long long
using namespace std;
int cnt,n,prime[1001000];
LL phi[1001000];
bool v[1001000];
void quick_euler()
{
    phi[1]=1;
    for(int i=2;i<=N;i++)
    {
        if(!v[i])
        {
            prime[++cnt]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=cnt&&i*prime[j]<=N;j++)
        {
            v[i*prime[j]]=1;
            if(i%prime[j]==0)
            {
                phi[i*prime[j]]=phi[i]*prime[j];
                break;
            }
            else
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
        }
    }
    phi[1]=2;
    for(int i=1;i<=N;i++)
        phi[i]+=phi[i-1];
}
int main()
{
    quick_euler();
    while(scanf("%d",&n)!=EOF)
    {
        printf("%lld\n",phi[n]*2-1);
    }
    return 0;
}