程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
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. 下一頁:
關於C++
C++ 內存布局：深入理解C++內存布局

1、虛函數簡介 虛函數的實現要求對象攜帶額外的信息，這
二叉樹的建立與遍歷（二）（c++實現）

【目標】建立如下所示的一棵二叉樹，並且輸出其對應的前序遍歷、
建立磁性窗體

一些著名的共享軟件不但功能卓著，而且在程序界面
leetcode筆記：3Sum Closest

一.題目描述二.解題技巧1.if target >=

分拆數組技巧應用

給你一個數組A[1..n]，請你在O(n)的時間裡構造一個新
muduo 與 boost asio 吞吐量對比

muduo (http://code.goog
相關文章
閱讀排行榜
poj 1845 Sumdiv (算術基本定理求一個數因子和) 動態漢化Windows技術原理分析 C++中函數模板(function template) 的 推進(forward) 問題 hihocoder1170（狀壓dp） sgu262：Symbol Recognition(狀壓DP) HDU 2091 空心三角形 C++ 11 右值引用以及std::move C++ 函數的重載 BZOJ 3878 Ahoi2014 奇怪的計算器 線段樹 Win32開發入門教程 LeetCode 21 Merge Two Sorted Lists
熱門圖文
C#新提供的一個操作符 RabbitMQ .NET消息隊列使用詳解，rabbitmq使用詳解 轉：什麼是即時編譯（JIT）！？OpenJDK HotSpot VM剖析，jitopenjdk Ｃ＃公共類收集 開發手記之實現web.config的快速配置 php 動態添加記錄 Java中的DeskTop類 C#3.0筆記(一)預備知識之Delegate
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved