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

HDU 1695 GCD (容斥原理+質因數分解)

編輯：C++入門知識

HDU 1695 GCD (容斥原理+質因數分解)

先進行預處理，對每一個數分解質因數。

然後將因為若gcd(x,y)==z,那麼gcd(x/z,y/z)==1，又因為不是z的倍數的肯定不是，所以不是z的倍數的可以直接去掉，所以只要將b和d除以k，然後就轉化成了求兩個范圍中互質的對數了。這時候可以枚舉1~b，然後用容斥原理找1~d范圍內的與枚舉數互質的數的個數，為了避免重復，只要再限定下大小關系就可以了，具體見代碼。

代碼如下：

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define LL __int64
const int mod=1e9+7;
const int INF=0x3f3f3f3f;
LL ans;
LL a, b, c, d;
vectorvec[110000];
void dfs(LL i, int cur, int cnt, LL tmp)
{
        tmp*=(LL)vec[i][cur];
        if(cnt&1) {
                ans+=(LL)min(d,i)/tmp;
        } else {
                ans-=(LL)min(d,i)/tmp;
        }
        for(int j=cur+1; j1)
                        vec[i].push_back(x);
        }
}
int main()
{
        int t, i, j, num=0;
        LL sum, k;
        init();
        scanf("%d",&t);
        while(t--) {
                scanf("%I64d%I64d%I64d%I64d%I64d",&a,&b,&c,&d,&k);
                num++;
                if(!k) {
                        printf("Case %d: 0\n",num);
                        continue ;
                }
                b/=k;
                d/=k;
                if(b