首页 > 代码库 > HDU 1695

HDU 1695

2024-08-02 00:53:44   217人阅读

http://acm.hdu.edu.cn/showproblem.php?pid=1695

x是[1,b]，y是[1,d]，求GCD(x,y)=k的对数（x,y无序）

对x，y都除以k，则求GCD(x,y)=1

此时枚举x，问题转化为[1,d]区间内与x互素的数字个数，这个问题是hdu 4135

有一个特殊的地方是x，y无序，对于这点只要保证x始终小于y就可以了

特判k=0

#include <iostream>#include <cstdio>#include <cstring>#include <vector>using namespace std;typedef __int64 ll;vector <int> v;int b,d,k;int main(){    int T;    scanf("%d",&T);    for(int cas=1;cas<=T;cas++){        scanf("%*d%d%*d%d%d",&b,&d,&k);        if(!k){            printf("Case %d: 0\n",cas);            continue;        }        b/=k;d/=k;        if(b>d)swap(b,d);        int i;        ll ans=0;         for(i=1;i<=b;i++){            int temp=i;            v.clear();            for(int j=2;j*j<=i;j++){                if(i%j==0){                    v.push_back(j);                    while(i%j==0)i/=j;                }            }            if(i>1)v.push_back(i);            int m=v.size();            i=temp;            ll res=0;             for(int j=1;j<(1<<m);j++){                int cnt=0;                ll val=1;                for(int k=0;k<m;k++){                    if(j&(1<<k)){                        cnt++;                        val*=v[k];                    }                }                if(cnt&1)res+=d/val-(i-1)/val;                else res-=d/val-(i-1)/val;            }            ans+=(d-i+1)-res;        }        printf("Case %d: %I64d\n",cas,ans);    }    return 0;}
View Code

 

HDU 1695


联系
我们