程序師世界是廣大編程愛好者互助、分享、學習的平台，程序師世界有你更精彩！
設為首頁 加入收藏
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> hdu3388Coprime 二分+容斥原理

hdu3388Coprime 二分+容斥原理

編輯：C++入門知識

hdu3388Coprime 二分+容斥原理


//找第k個和n，m互質的數
//由容斥原理可得
//在[1,x]范圍內且與n不互質的數的個數為：
//對於所有的n的素數因子：和一個素數因子不互質的個數-兩個素數因子相乘的個數+三個素數因子相乘的個數-.....
//對於x越大，在[1 , x]范圍內的與n,m互質的數越多，所以存在單調性，可以用二分找到剛好有k個數和n,m互質
#include
#include
#include
#include
using namespace std ;
typedef __int64 ll ;
const int maxn = 100010 ;
const int inf = 1e9 ;
mapma ;
ll p[maxn] ;
int len ;
void getprime(ll n)
{
for(int i = 2;i*i <= n;i++)
{
if(n%i == 0 && !ma[i])
{
p[++len] = i ;
ma[i] = 1;
}
while(n%i == 0)n/=(ll)i ;
}
if(n > 1 && !ma[n]){p[++len] = n;ma[n]=1;}
}
ll dfs(int pos , ll n)
{
ll ans = 0 ;
for(int i = pos ;i <= len ;i++)
ans += n/p[i] - dfs(i+1 , n/p[i]) ;
return ans ;
}
ll find(ll l , ll r , ll num )
{
while(l <= r)
{
ll mid = (l+r) >> 1 ;
if((mid - dfs(1 , mid)) < num)
l = mid + 1 ;
else r = mid - 1;
}
return l ;
}
int main()
{
// freopen("in.txt","r",stdin) ;
// freopen("out.txt","w" ,stdout) ;
int T ;int cas = 0 ;
int n , m ;int k ;
scanf("%d" , &T) ;
while(T--)
{
scanf("%d%d%d" ,&n , &m , &k) ;
len = 0 ;
ma.clear() ;
getprime((ll)(n));
getprime((ll)(m));
ll ans = find(1 , (ll)inf*(ll)inf, (ll)k);
printf("Case %d: " , ++cas) ;
printf("%I64d\n" , ans) ;
}
return 0;
}

  1. 上一頁:
  2. 下一頁:
C++入門知識
HDUJ 1272 小希的迷宮 並查集

HDUJ 1272 小希的迷宮 並查集 小希
exec替換進程印象

exec替換進程印象 概述在進程的創建上UNIX/Lin
在已有軟件加殼保護 下實現 Inline hook，inlinehook

在已有軟件加殼保護 下實現 Inline hook，inli
C++ 實現01背包動態規劃，01背包

C++ 實現01背包動態規劃，01背包簡述一下01背包： &
利用牛頓級數求圓周率小數點後15位小數，牛頓圓周率

利用牛頓級數求圓周率小數點後15位小數，牛頓圓周率十八世紀，
HDU 4756 Install Air Conditioning（次小生成樹）

HDU 4756 Install Air Condition
相關文章
閱讀排行榜
探討C++ 變量生命周期、棧分配方式、類內存布局、Debug和Release程序的區別（一） C++之父力作學習筆記5——運算符重載 Hoj 2183 Extrusion Codeforces Round #268 (Div. 1)A（構造） 五周 項目3 對象數組操作長方柱類 LeetCode 278 First Bad Version（第一個壞版本）（二分法）（*） 枚舉與剪枝_觀察算式（比標准答案還要牛B） WritePrivateProfileString 設置為程序當前路徑的方法 hdu4279 Number-------天津網絡賽 打表找規律 uboot中timer定時器的設置 c++中繼承問題小結
熱門圖文
建造者模式-Delphi述 C#中枚舉類型的作用 leetcode筆記：Count and Say HDU 4351 C語言學習016:單鏈表，c語言學習016單鏈 c#-求解:C# 操作在word,將richtextbox內容粘貼到word時剪貼板報錯 mfc-MFC控件綁定變量時候為什麼找不到我建立的類別 OWC生成Excel的效能優化(2)
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved