2012-12-16 18:50:12Morris
[UVA][因數] 12573 - Sohel Sir's Assignment
Sohel Sir's Assignment
Sohel sir gave an assignment in CSE-315 course instead of a class test. The assignment was
to make questions and provide corresponding answers from the chapters 2, 3, 4, 5. Each
student is assigned chapter no y according to the formula:
| Sohel Sir's Assignment |
y = (Roll % 4) + 2
I.e. he has to make questions and answers from chapter y. According to this rule, Roll 4 was
supposed to make questions and answers from chapter 2 as (4 % 4) + 2 = 2 and Roll 35 was
assigned to chapter 5 as (35 % 4) +2 = 5. In the meantime, roll 35 had already made the
questions & answers from chapter 5 and Roll 4 got the complete assignment of roll 35. So to
copy that assignment Roll 4 wanted to change the divisor 4 of the formula to some number m
such that his assignment changes to chapter 5 , that is (4 % m) + 2 = 5. But he failed to find
such number. Now, your problem is similar to the above problem.
Given two number x and y you have to find a positive number m such that (x % m) + 2 = y. If multiple m is possible, choose the minimum one. If no answer is found print `Impossible'.
Input
First line of input will contain the number of test cases, T
125. Then there follows T lines,
each containing two integers x (
0x1012) and y (
2yx + 2).
Output
For each case, print m, if m is found. Otherwise print `Impossible' (without quotes). See the samples given below for exact formatting.
Sample Input
4 4 5 35 5 4 2 11 5
Sample Output
Impossible 4 1 4
Problem Setter: Mohammad Hafiz Uddin
Alternate Solution: Radi Muhammad Reza
x%m+2 = y
x%m = y-2
x = km + y-2
x-y+2 = km
分解 x-y+2 即可，如果 x-y+2 == 0，輸出 x+1。
#include <stdio.h>
#include <math.h>
int main() {
scanf("%*d");
long long x, y;
int i;
while(scanf("%lld %lld", &x, &y) == 2) {
long long n = x-(y-2), sq;
sq = (long long)sqrt(n);
if(n == 0) {
printf("%lld\n", x+1);
continue;
}
int flag = 0;
long long mn;
for(i = 1; i <= sq; i++) {
if(n%i == 0) {
if(x%i+2 == y) {
if(!flag) mn = i, flag = 1;
if(i < mn) mn = i;
}
if(x%(n/i)+2 == y) {
if(!flag) mn = n/i, flag = 1;
if(n/i < mn) mn = n/i;
}
}
if(flag && i > mn) break;
}
if(flag)
printf("%lld\n", mn);
else
puts("Impossible");
}
return 0;
}