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
公開 測資點#0 (20%): 3.0s , <1K
公開 測資點#1 (20%): 3.0s , <1K
公開 測資點#2 (20%): 3.0s , <1K
公開 測資點#3 (20%): 3.0s , <1K
公開 測資點#4 (20%): 3.0s , <1K
| ID | User | Problem | Subject | Hit | Post Date |
| 31779 |
|
a258 | 397 | 2022-08-18 22:05 |