程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> 關於C++ >> HDU 1695 GCD (容斥原理+質因數分解)

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

編輯:關於C++

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

然後將因為若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

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved