CodeForces 1521A 題目翻譯+思路詳解+樣例程式

CodeForces 1521A

• 題目
• 思路整理
• • 資料的類型選擇
• 樣例程式

題目

原文描述：

Nastia has 2 positive integers A and B. She defines that:

• The integer is good if it is divisible by A⋅B；
• Otherwise, the integer is nearly good, if it is divisible by A.

For example, if A=6 and B=4, the integers 24 and 72 are good, the integers 6, 660 and 12 are nearly good, the integers 16, 7 are neither good nor nearly good.

Find 3 different positive integers x, y, and z such that exactly one of them is good and the other 2 are nearly good, and x+y=z.

Input：

The first line contains a single integer t (1≤t≤10 000) — the number of test cases.

The first line of each test case contains two integers A and B (1≤A≤106, 1≤B≤106) — numbers that Nastia has.

Output：

For each test case print:

• “YES” and 3 different positive integers x, y, and z (1≤x,y,z≤1018) such that exactly one of them is good and the other 2 are nearly good, and x+y=z.
• “NO” if no answer exists.

You can print each character of “YES” or “NO” in any case.

If there are multiple answers, print any.

input
3
5 3
13 2
7 11

output
YES 10 50 60
YES 169 39 208
YES 28 154 182

Note：

In the first test case: 60 — good number; 10 and 50 — nearly good numbers.

In the second test case: 208 — good number; 169 and 39 — nearly good numbers.

In the third test case: 154 — good number; 28 and 182 — nearly good numbers.

翻譯描述：

Nastia有兩個正整數A、B。她做了如下定義：

• 如果一個整數能被A·B整除那麼表明它是好的；
• 除此之外，一個整數如果能夠被A整除的數就表明它是次好的。

例如，如果A=6并且B=4,那麼整數24和72是好的，整數6、660、還有12都是次好的，整數16、7它們既不是好的也不是次好的。

找出3個不同的正整數x、y與z使得其中一個是好的并且另外兩個都是次好的，而且x+y=z。

輸入：

第一行有一個正數t(1≤t≤10 000) —測試樣例的數量。

每個測試樣例的第一行都包括兩個正數A與B (1≤A≤106, 1≤B≤106) — Nastia擁有的數。

輸出：

對于每一個測試樣例輸出：

• "YES"與三個不同的正整數x,y,z(1≤x,y,z≤1018)使得其中一個整數是好的，另外兩個是次好的，并且x+y=z。
• "NO"如果不存在。

你可以在相應的情況輸出"YES" 或者 “NO”。

如果答案有許多個，那麼輸出其中一個。

input
3
5 3
13 2
7 11

output
YES
10 50 60
YES
169 39 208
YES
28 154 182

提示：

第一個測試樣例：60 — 好的；10和50 — 次好的。

第二個測試樣例：208 — 好的；169和39 — 次好的。

第三個測試樣例：154 — 好的；18和182次好的。

思路整理

由題意整理關鍵資訊如下

1. 次好的數一定都是A的倍數
2. 好的數一定是A*B的倍數
3. x、y、z一定是3個不同的整數

由于在這三個不同的整數裡其中一個是好的（能被A*B整除）并且另外兩個是次好的（能被A整除），可見A出現的頻率特别高于是我們找出這三個數與A的關系。易知x、y、z一定都是A的倍數，且要求其中一個數必須是好的，最簡便的就是我們将好的數作為加數或者被加數，因為如果作為和的話就會比較難拼湊，并且A的倍數與A的倍數相加一定為A的倍數如：aA+bA=(a+b)A。故我們在這裡選擇好的作為被加數，最簡單的方法選擇A作為加數。

這樣的話我們就可以得到一個x+y=z的式子滿足上述三個條件了。其中x=A；y=A*B，那麼z=A *（B+1）。（注意當B=1的情況，由于給定的資料範圍裡 1≤B≤106。當B=1時會使得x=y）

資料的類型選擇

當然最後我們還需要考慮資料的邊界問題。

• 測試樣例數t(1≤t≤10 000) ，使用int型即可。
• 輸入值A、B (1≤A≤106, 1≤B≤106)，使用int型即可。同理x也可使用int型。
• 由于y、z為A與B或（B+1）的成績，這使得資料超出int型可存儲的範圍。故我們使用long long來存儲。

樣例程式

#include<iostream>

using namespace std;

int main() {
	int iTest = 0;//測試樣例個數
	cin >> iTest;
	while (iTest--) {
		int iA, iB;
		cin >> iA;
		cin >> iB;
		if (iB == 1) { //不考慮B=1的情況，因為當B=1時會使得x=y
			cout << "NO" << endl;
			continue;
		}
		cout << "YES" << endl;
		long long x = iA, y = iA * iB, z = (iB + 1) * iA;
		if (x != y)//判斷x與y是否相同，由于B大于1是以不會産生x、y、z都相同的情況
			cout << x << ' ' << y << ' ' << z << endl;
	}
	return 0;
}