題目描述

Hanks 博士是 BT（Bio-Tech，生物技術) 領域的知名專家，他的兒子名叫 Hankson。現在，剛剛放學回家的 Hankson 正在思考一個有趣的問題。

今天在課堂上，老師講解了如何求兩個正整數?c1??和?c2??的最大公約數和最小公倍數。現在 Hankson 認為自己已經熟練地掌握了這些知識，他開始思考一個“求公約數”和“求公倍數”之類問題的“逆問題”，這個問題是這樣的：已知正整數?a0?,a1?,b0?,b1?，設某未知正整數?x?滿足：

1. x?和?a0??的最大公約數是?a1?；

2. x?和?b0??的最小公倍數是?b1?。

Hankson 的“逆問題”就是求出滿足條件的正整數?x。但稍加思索之后，他發現這樣的?x?并不唯一，甚至可能不存在。因此他轉而開始考慮如何求解滿足條件的?x?的個數。請你幫助他編程求解這個問題。

輸入格式

第一行為一個正整數?n，表示有?n?組輸入數據。接下來的n?行每行一組輸入數據，為四個正整數?a0?,a1?,b0?,b1?，每兩個整數之間用一個空格隔開。輸入數據保證?a0??能被?a1??整除，b1??能被?b0??整除。

輸出格式

共?n?行。每組輸入數據的輸出結果占一行，為一個整數。

對于每組數據：若不存在這樣的?x，請輸出?0，若存在這樣的?x，請輸出滿足條件的?x?的個數；

輸入輸出樣例

輸入 #1復制

2 
41 1 96 288 
95 1 37 1776 

輸出 #1復制

6 
2

說明/提示

【樣例解釋】

第一組輸入數據，x?可以是?9,18,36,72,144,288，共有?6?個。

第二組輸入數據，x?可以是?48,1776，共有?2?個。

【數據范圍】

• 對于?50%?的數據，保證有?1≤a0?,a1?,b0?,b1?≤10000?且?n≤100。
• 對于?100%?的數據，保證有?1≤a0?,a1?,b0?,b1?≤2×109?且?n≤2000。

NOIP 2009 提高組 第二題

代碼實現;

#include<iostream>
#include<cmath>
using namespace std;
int gongyue(int i,int a0)
{
?? ?int j,k=1;
?? ?for(j=1;j<=min(i,a0);j++)
?? ?{
?? ??? ?if(i%j==0 && a0%j==0)
?? ??? ?{
?? ??? ??? ?k=j;
?? ??? ?}
?? ?}
?? ?return k;
}
int gongbei(int i,int b0)
{
?? ?int j,k=1;
?? ?for(j=min(i,b0);j<=i*b0;j++)
?? ?{
?? ??? ?if(j%i==0 && j%b0==0)
?? ??? ?{
?? ??? ??? ?k=j;
?? ??? ??? ?break;
?? ??? ?}
?? ?}
?? ?return k;
}
int main()
{
?? ?int n,a0,a1,b0,b1;
?? ?int i,j,k;
?? ?cin>>n;
?? ?while(n--)
?? ?{ ? int count=0;
?? ??? ?cin>>a0>>a1>>b0>>b1;
?? ??? ?for(i=1;i*i<=b1;i++)
?? ??? ?{
?? ??? ??? ?if(b1%i==0)
?? ??? ??? ?{
?? ??? ??? ?if((gongyue(i,a0)==a1) && (gongbei(i,b0)==b1))
?? ??? ??? ?{
?? ??? ??? ??? ?count++;
?? ??? ??? ??? ?//cout<<i<<endl;
?? ??? ??? ?}
?? ??? ??? ?if(i!=b1/i)
?? ??? ??? ?{
?? ??? ??? ??? ?j=b1/i;
?? ??? ??? ??? ?if((gongyue(j,a0)==a1) && (gongbei(j,b0)==b1))
?? ??? ??? ?{
?? ??? ??? ??? ?count++;
?? ??? ??? ??? ?//cout<<i<<endl;
?? ??? ??? ?}
?? ??? ??? ??? ?
?? ??? ??? ? }?
?? ??? ? ? ?}
?? ??? ? ? ?
?? ??? ? ? ?
?? ??? ?}
?? ??? ?cout<<count<<endl;
?? ?}
?? ?return 0;
?}?