程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> HDU 1695 GCD 歐拉函數+容斥原理+質因數分解

HDU 1695 GCD 歐拉函數+容斥原理+質因數分解

編輯：C++入門知識

HDU 1695 GCD 歐拉函數+容斥原理+質因數分解

題意：在[a,b]中的x，在[c,d]中的y，求x與y的最大公約數為k的組合有多少。（a=1, a <= b <= 100000, c=1, c <= d <= 100000, 0 <= k <= 100000）

思路：因為x與y的最大公約數為k，所以xx=x/k與yy=y/k一定互質。要從a/k和b/k之中選擇互質的數，枚舉1~b/k，當選擇的yy小於等於a/k時，可以選擇的xx數為Euler(yy),當yy大於a/k時，就要用容斥原理來找到yy的質因數，在a/k范圍內找到與yy互質的數。

代碼：

#include 
#include 
#include 
#include 
#include
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define PI acos(-1.0)
#define maxn 1<<20
#define INF 0x7fffffff
#define eps 1e-8
typedef long long LL;
typedef unsigned long long ULL;
using namespace std;
LL ans=0;
LL S=0;
LL sum2;
LL euler[100050];
void init()
{
    memset(euler,0,sizeof(euler));
    euler[1] = 1;
    for(int i = 2; i <= 100000; i++)
        if(!euler[i])
            for(int j = i; j <= 100000; j += i)
            {
                if(!euler[j])
                    euler[j] = j;
                euler[j] = euler[j]/i*(i-1);
            }
}
void factor(int n,int a[maxn],int b[maxn],LL &tt)
{
    int temp,i,now;
    temp=(int)((double)sqrt(n)+1);
    tt=0;
    now=n;
    for(i=2; i<=temp; i++)
    {
        if(now%i==0)
        {
            a[++tt]=i;
            b[tt]=0;
            while(now%i==0)
            {
                ++b[tt];
                now/=i;
            }
        }
    }
    if(now!=1)
    {
        a[++tt]=now;
        b[tt]=1;
    }
}
int dfs(int aa[],int pos,int res,int sum,int b,int tot)//res乘積，sum乘數的個數
{
    if(pos+1<=tot)
        dfs(aa,pos+1,res,sum,b,tot);
    sum++;
    res*=aa[pos];
    if(sum%2)
        sum2+=b/res;
    else
        sum2-=b/res;
    if(pos+1<=tot)
        dfs(aa,pos+1,res,sum,b,tot);
    return 0;
}
int main()
{
    int T,tt=0,aa[40],bb[40];
    init();
    while(~scanf(%d,&T))
    {
        tt=0;
        while(T--)
        {
            tt++;
            int a,b,c,d,k;
            scanf(%d%d%d%d%d,&a,&b,&c,&d,&k);
            printf(Case %d: ,tt);
            if(k==0)
            {
                printf(0
);
                continue;
            }
            if(d