程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> 求出所有的正整數對 使他們最大公約數為n,最小公倍數為m

求出所有的正整數對 使他們最大公約數為n,最小公倍數為m

編輯:C++入門知識

求出所有的正整數對 使他們最大公約數為n,最小公倍數為m


 

 

大意就是 求出所有的正整數對 使他們最大公約數為n,最小公倍數為m。(1 <= n, m <= 10^10)

可以將問題轉化為 : 設a,b就是那個整數對,n, a, b, m, 這4個數都是可以被n整除的,可以都除以n, 題目轉化為求出 最大公約數為1, 最小公倍數為m/n的對數 。

也就是求出在1到m/n裡 乘積為m/n且互質的對數。可以在O(sqrt (m/n) )內解決。

 

 

#include 
#include 
#include 
#include 
#include 
#include 
#define MAX 0x3f3f3f3f
#define N 2000005
typedef long long LL;
using namespace std;

int T;
LL n, m;
LL gcd(LL a, LL b) {
    return b == 0 ? a : gcd(b, a % b);
}

int main()
{
    cin>>T;while(T--) {
        cin >> n >> m;
        if(m % n) {
            printf(0
);
            continue;
        }
        LL x = m / n;
        int ans = 0;
        for(LL i = 1; i <= (LL)sqrt(x); i++) {
            if(x % i == 0) {
                LL j = x / i;
                if(gcd(i, j) == 1) ans++;
            }
        }
        printf(%d
, ans);
    }
    return 0;
}

 

 

??

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