柚子快報(bào)激活碼778899分享：算法 藍(lán)橋杯gcd匯總

http://yzkb.51969.com/

gcd3014

問(wèn)題描述

小明和小紅是一對(duì)戀人，他們相愛(ài)已經(jīng)三年了，在今年的七夕節(jié)，小明準(zhǔn)備給小紅一個(gè)特殊的禮物。他想要送給小紅一些數(shù)字，讓小紅算出有多少對(duì)正整數(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ù) 。

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

輸入格式

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

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

輸出格式

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

樣例輸入

2

2 3 6

4 5 7

樣例輸出?

4

2

解析

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

代碼

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 x

int n = (x + d * g) / c; // 計(jì)算a*b

if (n % g != 0) continue; // Skip if g does not divide n

int phi = eulerPhi(n / g); // Calculate phi(n/g), the count of numbers coprime with n/g

count += 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)常會(huì)看到針對(duì)某一個(gè)觀點(diǎn)同意與否的民意調(diào)查以及結(jié)果。例如，對(duì)某一觀點(diǎn)表示支持的有 1498 人，反對(duì)的有 902 人，那么贊同與反對(duì)的比例可以簡(jiǎn)單的記為 1498:902。

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

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

輸入描述

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

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

輸出描述

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

輸入輸出樣例

示例

輸入

1498 902 10

輸出

5 3

代碼

import java.util.Scanner;

// 1:無(wú)需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

for(int j=1;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)在，剛剛放學(xué)回家的 Hankson 正在思考一個(gè)有趣的問(wèn)題。

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

x?和?a0??的最大公約數(shù)是?a1?； x?和?b0??的最小公倍數(shù)是?b1?。

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

輸入描述

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

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

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

輸出描述

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

對(duì)于每組數(shù)據(jù)：若不存在這樣的?x，請(qǐng)輸出 0；若存在這樣的?x，請(qǐng)輸出滿足條件的?x?的個(gè)數(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 stub

Scanner 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ù)更新）

柚子快報(bào)激活碼778899分享：算法 藍(lán)橋杯gcd匯總

http://yzkb.51969.com/

精彩文章