A simple Blog for wyx I've been down the bottle hoping.
BZOJ 2818 Gcd
发表于: | 分类: Oi | 评论:0 | 阅读:130

传送门
题目大意就是求在给定范围内
$gcd(x,y)=prime$
的所有的有序$(x,y)$的对数

分析
我们令$gcd(x,y) =k$,$k$是质数,那么就有$\gcd(x/k,y/k)=1$
不妨先让$(x,y)$中的$y>x$
问题就变成了求$y/k$中与其互质的数的个数
显然是$\phi(y/k)$所以我们只需要对$\phi$求一个前缀和,然后扫一遍$N$之前的全部质数统计下就行了
下面是代码

#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
#define N 10000000+5
using namespace std;
 
int prime[N],cnt;
bool f[N];
int phi[N];
long long sum[N];
int n;
void init()
{
    phi[1]=1;
    register int i;
    for(i=2;i<=n;++i)
    {
        if(!f[i])
        {
            prime[++cnt] = i;
            phi[i] = i-1;
        }
        for(int j=1;(long long)prime[j]*i <= n; ++j)
        {
            f[prime[j]*i] = 1;
            if(i%prime[j]==0)
            {
                phi[prime[j]*i] = phi[i] * prime[j];
                break;
            }
            else
                phi[prime[j]*i] = phi[i] * (prime[j]-1);
        }
    }
}
 
int main()
{
    cin>>n;
    init();
//  for(int i=1;i<=10;++i)
//s     cout<<phi[i]<<" ";
    for(int i=1;i<=n;++i)
        sum[i] = sum[i-1] + phi[i];
    long long ans = 0;
    for(int i=1;i<=cnt;++i)
        ans += sum[n/prime[i]]*2-1;//1 1 ->-1
    cout<<ans;
}   
Title - Artist
0:00

站点地图 网站地图
Copyright © 2015-2017 A simple Blog for wyx
Powered by Typecho自豪的采用Sgreen主题

TOP