a258. NCPC2011 Problem F Inverse Affine Transform
內容 ：
Problem F
Inverse Affine Transform
Input File: pf.in
Time Limit: 3 seconds
Let m be a positive integer, under a modular arithmetic, an affine transform
on the set S = {0,1,2,…,m-1} can be defined as
y ≡ ax+b mod m (1)
Some permutations on an integer set S could be implemented based on the
above affine transform with parameters a and m being relatively prime, that
is, their greatest common divisor gcd(a,m) = 1. If gcd(a, m) = 1, the inverse
transform exists which is also an affine transform, say,
x ≡ cy+d mod m (2)
This problem asks you to write a program to dectect and compute the
inverse transform of an affine transform with the given parameters m, a, b.
輸入說明
：
number of test cases to come. Each test data set consists of a line of three
positive integers m, a, b, respectively. Note that 3 ≦ K ≦ 5 and m ≦ 220 =
10485676 in this problem.
輸出說明
：
K lines, each line consist of “No inverse, gcd(a,m)=” followed by the value
gcd(a,m) if gcd(a,m) > 1 or the values of c and d, where 0 < c, d < m, if
gcd(a,m) = 1
範例輸入 ：
5 5 2 1 16 6 5 262144 13131 128 1048576 2004 8000 1048576 301 100
範例輸出 ：
3 2 No inverse, gcd(a,m)=2 15971 52864 No inverse, gcd(a,m)=4 456357 501644
提示
：
出處
：
作法 : 數學
我不會推導，但是我猜出來了
a*c ≡ 1 mod m, ad+b ≡ 0 mod m, cb+d ≡ 0 mod m
又有給 c, d < m, 直接 O(m) 搜尋吧, k <= 5, m <= 1000000
很肯定的不會 TLE
/**********************************************************************************/
/* Problem: a258 "NCPC2011 Problem F Inverse Affine Transform" from NCPC2011 */
/* Language: C (561 Bytes) */
/* Result: AC(23ms, 306KB) judge by this@ZeroJudge */
/* Author: morris1028 at 2011-10-16 17:28:37 */
/**********************************************************************************/
#include<stdio.h>
int gcd(int x, int y) {
int tmp;
while(x%y) {
tmp = x, x = y, y = tmp%y;
}
return y;
}
int main() {
long long K, a, b, c, d, m, i;
scanf("%lld", &K);
while(K--) {
scanf("%lld %lld %lld", &m, &a, &b);
if(gcd(m, a) != 1) {
printf("No inverse, gcd(a,m)=%d\n", gcd(m, a));
continue;
}
for(i = 1; i < m; i++) {
if((a*i)%m == 1) {
c = i;
break;
}
}
for(i = 1; i < m; i++) {
if((a*i+b)%m == 0) {
d = i;
break;
}
}
printf("%lld %lld\n", c, d);
}
return 0;
}