麻豆小视频在线观看_中文黄色一级片_久久久成人精品_成片免费观看视频大全_午夜精品久久久久久久99热浪潮_成人一区二区三区四区

首頁 > 學院 > 開發設計 > 正文

寒假16:算法訓練 Hankson的趣味題

2019-11-14 12:40:16
字體:
來源:轉載
供稿:網友

 算法訓練 Hankson的趣味題  時間限制:1.0s   內存限制:64.0MB      錦囊1枚舉或數論方法。錦囊2x是a1的倍數,b1的約數,可以枚舉b1所有的約數來判斷是否滿足條件。 也可以使用數論的方法,將a0, a1, b0, b1分解因數,可以找到x對于每個質因子的范圍,根據這個可以得到答案的公式(將每個質因子的范圍相乘)。問題描述  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 的個數;樣例輸入241 1 96 28895 1 37 1776樣例輸出62樣例說明  第一組輸入數據,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,000,000,000 且n≤2000。常規的窮舉法,超時了。只過了50%的數據。沒學過高等數學,不明白提示的意思|

代碼:

import java.util.Scanner;public class Hankson的趣味題 {	public static void main(String[] args) {				Scanner sc=new Scanner(System.in);		int n=sc.nextInt();		int[] data=new int[n];				for (int i = 0; i < data.length; i++) {			int max=0;			int a0=sc.nextInt();			if(a0>max)max=a0;			int a1=sc.nextInt();			if(a1>max)max=a1;			int b0=sc.nextInt();			if(b0>max)max=b0;			int b1=sc.nextInt();			if(b1>max)max=b1;			data[i]=getCount(a0,a1,b0,b1,max);		}		for (int i = 0; i < data.length; i++) {			System.out.PRintln(data[i]);		}	}	private static int getCount(int a0, int a1, int b0, int b1,int max) {		int count=0;		for (int i = 1; i <= max; i++) {			if(gcd(i,a0)==a1&&i*b0/gcd(i,b0)==b1)				count++;		}		return count;	}	private static int gcd(int i, int j) {		if(i%j==0)			return j;		return gcd(j,i%j);	}}


發表評論 共有條評論
用戶名: 密碼:
驗證碼: 匿名發表
主站蜘蛛池模板: 国产成人精品二区 | 亚洲国产美女视频 | 精品一区二区三区四区在线 | 亚洲成人第一页 | 欧美一级免费视频 | 久草在线视频网 | 免费毛片儿 | 91精品国产乱码久久久久 | 黄色免费不卡视频 | 国产亚洲精品久久久久5区 男人天堂免费 | 在线成人免费观看视频 | 狠狠色成色综合网 | 欧美成人性生活片 | 欧美成人一二三区 | 欧美综合在线观看 | 久久亚洲线观看视频 | 国产精品视频自拍 | 在线97视频 | 免费永久在线观看黄网 | 免费嗨片首页中文字幕 | 国产在线看一区 | 久久99综合 | 国产精品18久久久久久久 | 538任你躁在线精品视频网站 | 久久经典 | 性少妇videosexfreexxx片 | 久久精品视频日本 | 中文字幕一区二区三区久久 | 国产美女做爰免费视 | 久久午夜免费视频 | 中文欧美日韩 | 九九热在线免费观看视频 | 成人福利在线免费观看 | 在线观看中文字幕av | 色中色综合网 | 久久精品视频一区二区三区 | 成人在线视频免费播放 | 欧美片a | 一级毛片电影网 | 欧美日韩成人一区二区 | 免费一级特黄欧美大片勹久久网 |