频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
HDU 1695 GCD 欧拉函数+容斥原理
2012-08-06 05:31:00           
收藏   我要投稿
从1-b和1-d中各取一个数,使得其最大公约数为k。问有多少对。
因为是最大公约数k,所以不仅仅是拥有因子k。除了因子k之外是互质的。
转化成从1---b/k和1---d/k中取出互质的数对。
从一个区间里取出一个数,比他小的互质的部分可以通过欧拉函数搞定,另外一部分通过容斥原理实现。
[cpp] 
#include<iostream> 
#include<cstdio> 
#include<cstring> 
#include<queue> 
#include<vector> 
#include<cmath> 
#define LL  long long 
#define MOD 1000000007 
#define eps 1e-6 
#define N 100010 
#define zero(a)  fabs(a)<eps 
using namespace std; 
LL eular[N]; 
int prime[N][15],cnt[N]; 
void Prime(){ 
    for(int i=2;i<N;i++){ 
        if(eular[i]==i){ 
            eular[i]=i-1; 
            for(int j=2;j*i<N;j++){ 
                eular[i*j]=eular[i*j]*(i-1)/i; 
                prime[j*i][cnt[j*i]++]=i; 
            } 
        } 
        eular[i]+=eular[i-1]; 
    } 

void Init(){ 
    for(int i=1;i<N;i++) 
        eular[i]=i; 
    memset(cnt,0,sizeof(cnt)); 
    Prime(); 

LL dfs(int idx,int cur,int now){ 
    LL ret=0; 
    for(int i=idx;i<cnt[now];i++) 
        ret+=cur/prime[now][i]-dfs(i+1,cur/prime[now][i],now); 
    return ret; 

int main(){ 
    int t,cas=0; 
    Init(); 
    scanf("%d",&t); 
    while(t--){ 
        int a,b,c,d,k,l,r; 
        scanf("%d%d%d%d%d",&a,&b,&c,&d,&k); 
        if(k==0){ 
            printf("Case %d: 0\n",++cas); 
            continue; 
        } 
        l=b/k; 
        r=d/k; 
        if(l>r) 
            swap(l,r); 
        //1-l通过欧拉函数求出 
        LL ans=eular[l]; 
        //1-l中与i互质的数 
        for(int i=l+1;i<=r;i++) 
            ans+=l-dfs(0,l,i); 
        printf("Case %d: %I64d\n",++cas,ans); 
    } 
    return 0; 

作者:ACM_cxlove
点击复制链接 与好友分享!回本站首页
上一篇:hdu4334----多校联合4
下一篇:POJ 1751 Highways 最小生成树
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站