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

hdu3388Coprime 二分+容斥原理

編輯：關於C++
//找第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++
C++文件編碼由GBK轉換UTF

在VS下面開發Cocos程序的時候，他的默認編碼是GBK的，
python 調用 C++ code

本文以實例code講解python 調用 C++的方法。1.
HDU 4002 Find the maximum （歐拉函數

 【題目大意】：給出一個整數n，求一個數x，x在1
GEEK學習筆記— —STL容器forward_list

簡介在頭文件 中定義namespace std {

CodeFx：一站式微軟開發技術解決方案

晚上在博客堂讀完VSTO寫的一篇文章，介紹了C
面試中的 10 大排序算法總結

面試中的 10 大排序算法總結前言查找和排序算法是算法的入門
相關文章
閱讀排行榜
判別剪貼板上所有可用的格式 二進制中1的個數以及時間比較 HDU 1402 A * B Problem Plus（FFT） Boost庫中的實用工具類使用入門 c++內存管理 LeetCode 21 Merge Two Sorted Lists C++：庫函數優先級隊列(priority_queue)輸出最小值 代碼 leetcode_Number of 1 Bits hdu 3631 Shortest Path（Floyd） UVA10325 C++ 范式工廠
熱門圖文
android-一個不可見的 LinearLayout 占據空間問題 怎麼在 Visual Studio 2013 上使用 Github COM原理及應用----COM對象和接口 php在字符串中查找另一個字符串 C語言基礎教程（三）輸入輸出函數及控制流程語句(8) Java Applet的應用技巧 使用 IntraWeb (4) Servlet數據緩存，servlet緩存
欄目導航
C++基礎知識C++入門知識關於C++
Copyright © 程式師世界 All Rights Reserved