青少年编程知识记录 codecoming

【题解】数学游戏

【题目描述】

Kri 喜欢玩数字游戏。 一天,他在草稿纸上写下了t 对正整数(x,y) ,并对于每一对正整数计算出了z=x*y*gcd(x,y);可是调皮的 Zay 找到了 Kri 的草稿纸,并把每一组的 y都擦除了,还可能改动了一些 z。

现在 Kri 想请你帮忙还原每一组的 y,具体地,对于每一组中的 x和 z,你需要输出最小的正整数 y,使得 z=x*y*gcd(x,y)  。如果这样的 y不存在,也就是 Zay 一定改动了z ,那么请输出 -1。 注:gcd(x,y) 表示 x和 y的最大公约数,也就是最大的正整数 d,满足 既是x 的约数,又是 y的约数。

【输入描述】

第一行一个整数 t ,表示有 对正整数 x和z 。

 接下来 t 行,每行两个正整数 x和z ,含义见题目描述。

【输出描述】

对于每对数字输出一行,如果不存在满足条件的正整数y ,请输出-1 ,否则输出满足条件的最小正整 数 y。

【样例输入1】

1  10 240

【样例输出1】

12

【样例1解释】

x*y*gcd(x,y)=10*12*gcd(10,12)=240

【样例输入2】

3  5 30  4 8  11 11

【样例输出2】

6  -1  1

【数据范围】

对于20%的数据,t,x,z<=103。 

对于40%的数据,t<=103,  x<106,  z<=109。 

对于另30% 的数据,t<104 。 

对于另20% 的数据,x<106 。 

对于100%的数据,1<=t<=5*105, 1<=x<=109, 1<=z<=263

标签: noi online

作者:亿万年的星光 分类:题解目录 浏览:

【题解】王国比赛

【题目描述】

智慧之王 Kri 统治着一座王国。 这天 Kri 决定举行一场比赛,来检验自己大臣的智慧。 比赛由 n道判断题组成,有 m位大臣参加。现在你已经知道了所有大臣的答题情况,但尚未拿到答 案,于是你决定先行预测。 具体来说,对于第 i道题,有 x个大臣选对, y个大臣选错(显然有x+y=m ),如果x>y,那 么你预测这题答案为对,否则为错。为了方便,我们保证 m是奇数。 在统计完成后,你拿到了答案,你想知道通过你的预测方式你最后有几道题预测正确。

【输入描述】

第一行两个正整数 n,m,保证m 是奇数。 接下来 m行,每行n 个整数,第i 行第j个整数 aij代表第 i位大臣对第 j道题的答案, 1表示他选 对, 0表示他选错。 接下来1 行 n个整数, 表示比赛答案, 第i 个数 bi若为 1表示第i 道题答案是对,若为 0表示答案是 错。

【输出描述】

输出一个整数,表示你最后有几题预测正确。

【样例输入1】

3 3  1 0 1  0 1 1  0 1 0  1 1 1

【样例输出1】

2

【样例1解释】

第一题 你预测答案为错(即0),实际答案为1,预测错误。 

第二题 你预测答案为对(即1),实际答案为1,预测正确。

第三题 你预测答案为对(即1),实际答案为1,预测正确。 所以预测正确的题数为2。

【样例2输入】

5 6  1 0 1 1 1 0  0 1 0 1 1 1  0 0 1 0 1 0  1 0 1 0 1 0  0 1 0 1 0 0  1 0 1 0 1 0

【样例2输出】

4

【数据范围】

对于20%的数据,n<=5,m=1 。 

对于50%的数据,n<=10,m<=10 。 

对于100%的数据, n<=1000 , m<=1000,m为奇数 。