gcd3014

問題描述

小明和小紅是一對戀人，他們相愛已經(jīng)三年了，在今年的七夕節(jié)，小明準備給小紅一個特殊的禮物。他想要送給小紅一些數(shù)字，讓小紅算出有多少對正整數(shù)?(a,b)?滿足以下條件：

c×lcm(a,b)?d×gcd(a,b)=x其中?c,d,x?是小明給出的數(shù)gcd(a,b)?為 a,b?的最大公因lcm(a,b)?為?a,b?的最小公倍數(shù) 。

小明希望這個問題能夠考察小紅對于數(shù)論基礎(chǔ)知識的理解和運用，同時也希望小紅能夠在這個特殊的日子里感受到他對她的深情。請你幫助小明實現(xiàn)他的想法吧！

輸入格式

第一行包含一個正整數(shù)?T(1≤T≤103)，表示詢問的組數(shù)。

接下來?T?行，每行包含三個正整數(shù)?c,d,x（1≤c,d,x≤105）。

輸出格式

對于每組詢問，輸出一個正整數(shù)表示滿足條件的(a,b)?對數(shù)。

樣例輸入

2
2 3 6
4 5 7

樣例輸出?

4
2

解析

需要理解gcd（最大公因數(shù)）和lcm（最小公倍數(shù)）的性質(zhì)，并且能夠遍歷所有可能的正整數(shù)對(a, b)，計算滿足條件的數(shù)量。然而，直接遍歷所有可能的(a, b)對會導致時間復(fù)雜度過高，因此我們需要觀察題目中所給的不等式。

代碼

package lanqiaoyun;
import java.util.*;
public class gcd3014 {public static void main(String args[]) {Scanner scanner=new Scanner(System.in);int T = scanner.nextInt();while (T-- > 0) {int c = scanner.nextInt();int d = scanner.nextInt();int x = scanner.nextInt();System.out.println(countPairs(c, d, x));}scanner.close();}private static int countPairs(int c, int d, int x) {int count = 0;// gcd中所有的可能的元素for (int g = 1; g * g <= x; g++) {if (x % g != 0) continue; // Skip if g does not divide xint n = (x + d * g) / c; // 計算a*bif (n % g != 0) continue; // Skip if g does not divide nint phi = eulerPhi(n / g); // Calculate phi(n/g), the count of numbers coprime with n/gcount += phi; // Add phi(n/g) to the count for each valid g}return count;}// Calculate Euler's totient function phi(n)private static int eulerPhi(int n) {int result = n;for (int i = 2; i * i <= n; i++) {if (n % i == 0) {while (n % i == 0) {n /= i;}result -= result / i;}}if (n > 1) {result -= result / n;}return result;}public static long gcd(long a,long b) {return b==0?a:gcd(b,a%b);}public static long lcm(long a,long b) {return a/gcd(a,b)*b;}
}

gcd368

在社交媒體上，經(jīng)常會看到針對某一個觀點同意與否的民意調(diào)查以及結(jié)果。例如，對某一觀點表示支持的有 1498 人，反對的有 902 人，那么贊同與反對的比例可以簡單的記為 1498:902。

不過，如果把調(diào)查結(jié)果就以這種方式呈現(xiàn)出來，大多數(shù)人肯定不會滿意。因為這個比例的數(shù)值太大，難以一眼看出它們的關(guān)系。對于上面這個例子，如果把比例記為 5:3，雖然與真實結(jié)果有一定的誤差，但依然能夠較為準確地反映調(diào)查結(jié)果，同時也顯得比較直觀。

現(xiàn)給出支持人數(shù)?A，反對人數(shù)?B，以及一個上限?L，請你將?A?比?B?化簡為?′A′?比?′B′，要求在?′A′和 ‘B′均不大于?L?且?′A′和?′B′互質(zhì)（兩個整數(shù)的最大公約數(shù)是 1）的前提下，A′/B′≥A/B且A′/B′?A/B?的值盡可能小。

輸入描述

輸入共一行，包含三個整數(shù)?A，B，L，每兩個整數(shù)之間用一個空格隔開，分別表示支持人數(shù)、反對人數(shù)以及上限。

其中，1≤A≤106，1≤B≤106，1≤L≤100，A/B≤L。

輸出描述

輸出共一行，包含兩個整數(shù) ′A′，B′，中間用一個空格隔開，表示化簡后的比例。

輸入輸出樣例

示例

輸入

1498 902 10

輸出

5 3

代碼

import java.util.Scanner;
// 1:無需package
// 2: 類名必須Main, 不可修改public class Main {public static void main(String[] args) {Scanner scan = new Scanner(System.in);//在此輸入您的代碼...double a=scan.nextDouble();double b=scan.nextDouble();double l=scan.nextDouble();double min=100;int res1=0;int res2=0;for(int i=0;i<l;i++){for(int j=1;j<l;j++){double m=(double) a*1.0/b;double p=(double) i*1.0/j;if(p>=m&&gcd(i,j)==1&&p-m<=min){min=(p-m);//持續(xù)尋找更小的min，并更新res1=i;res2=j;}}}if(l==1) {res1=1;res2=1;System.out.println(res1+" "+res2);}else {System.out.println(res1+" "+res2);}scan.close();}public static double gcd(double a,double b ){return b==0?a:gcd(b,a%b);}}

gcd520

題目描述

Hanks 博士是 BT (Bio-Tech，生物技術(shù)) 領(lǐng)域的知名專家，他的兒子名叫 Hankson?，F(xiàn)在，剛剛放學回家的 Hankson 正在思考一個有趣的問題。

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

1. x?和?a0??的最大公約數(shù)是?a1?；

2. x?和?b0??的最小公倍數(shù)是?b1?。

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

輸入描述

第一行為一個正整數(shù)?n，表示有?n?組輸入數(shù)據(jù)。

接下來的?n?行每行一組輸入數(shù)據(jù)，為四個正整數(shù)a0?，a1?，b0?，b1?，每兩個整數(shù)之間用一個空格隔開。輸入數(shù)據(jù)保證 a0??能被?a1??整除，b1??能被?b0??整除。

其中，保證有1≤a0?，a1?，b0?，b1?≤2×109且n≤2000。

輸出描述

輸出共?n?行。每組輸入數(shù)據(jù)的輸出結(jié)果占一行，為一個整數(shù)。

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

輸入輸出樣例

示例 1

輸入

2
41 1 96 288
95 1 37 1776 

輸出

6
2

代碼

?

package lanqiaoyun;
import java.util.*;
public class gcd520 {public static void main(String[] args) {// TODO Auto-generated method stubScanner scan = new Scanner(System.in);//在此輸入您的代碼...int n=scan.nextInt();while(n-->0){long a0=scan.nextLong();long a1=scan.nextLong();long b0=scan.nextLong();long b1=scan.nextLong();int count=0;for(int x=0;x<=b1;x++){if(gcd(x,a0)==a1&&lcm(x,b0)==b1){count++;}}System.out.println(count);}scan.close();}public static long gcd(long x,long a0){return a0==0?x:gcd(a0,x%a0);}public static long lcm(long x,long b0){return x/gcd(x,b0)*b0;}
}

（后期持續(xù)更新）