GCD

2
1 3 1 5 1
1 11014 1 14409 9

Case 1: 9
Case 2: 736427

Hint
For the first sample input, all the 9 pairs of numbers are (1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (2, 3), (2, 5), (3, 4), (3, 5).

一道比较经典的题目，可以用容斥原理，也可以莫比乌斯反演，莫比乌斯反演暂时没实现，就是把b，d都除以k，然后查找互素对数，枚举+容斥，一个特判的trick纠结了一天，

被dream神三分钟就找到了，

代码：

#pragma comment(linker, "/STACK:102400000,102400000")
#include <stdio.h>
#include <iostream>
#include <algorithm>
#include <sstream>
#include <stdlib.h>
#include <string.h>
#include <limits.h>
#include <string>
#include <time.h>
#include <math.h>
#include <queue>
#include <stack>
#include <set>
#include <map>
using namespace std;
#define INF 0x3f3f3f3f
#define eps 1e-8
#define pi acos(-1.0)
typedef __int64 ll;
bool isprime[1001000];
ll prime[1001000],factor[1010];
void getprime(){
    memset(isprime,1,sizeof(isprime));isprime[1]=0;
    ll &cnt=prime[0];cnt=0;
    for(ll i=2;i<=1000000;i++){
        if(isprime[i])prime[++cnt]=i;
        for(ll j=1;j<=cnt&&i*prime[j]<=1000000;j++){
            isprime[i*prime[j]]=0;
            if(i%prime[j]==0)break;
        }
    }
//    cout<<prime[0]<<endl;
}
void getfactor(ll x){
    ll &cnt=factor[1000];cnt=0;
    for(ll i=1;i<=prime[0]&&prime[i]*prime[i]<=x;i++)
        if(x%prime[i]==0){
            factor[cnt++]=prime[i];
            while(x%prime[i]==0)x/=prime[i];
        }
    if(x>1)factor[cnt++]=x;
}
ll cal(ll x){
    ll cnt=factor[1000],ans=0;
    for(ll i=1;i<(1<<cnt);i++){
        ll pp=1,ss=0;
        for(ll j=0;j<cnt;j++)
            if(i&(1<<j)){
                ss++;pp*=factor[j];
            }
        if(ss%2)ans+=x/pp;
        else ans-=x/pp;
    }
    return x-ans;
}
int main()
{
     //freopen("data.in","r",stdin);
    // freopen("data.out","w",stdout);
     getprime();
     int T;scanf("%d",&T);
     for(int t=1;t<=T;t++){
         ll a,b,c,d,k;
         scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k);
         printf("Case %d: ",t);
         if(k==0){
             puts("0");continue;
         }
         ll ans=0;
         if(b>d)swap(b,d);b/=k;d/=k;
		 if(b)ans+=d;
         for(ll i=2;i<=b;i++){
             getfactor(i);
             ans+=cal(d)-cal(i);
         }
         cout<<ans<<endl;
     }
     return 0;
}

hdu 1695 容斥原理或莫比乌斯反演,布布扣,bubuko.com

hdu 1695 容斥原理或莫比乌斯反演

原文：http://blog.csdn.net/xianxingwuguan1/article/details/22901813