a258. NCPC2011 Problem F Inverse Affine Transform＠Morris' Blog

2011-10-16 21:18:35| 人氣513| 回應0 | 上一篇 | 下一篇

a258. NCPC2011 Problem F Inverse Affine Transform

推薦 0 收藏 0 轉貼0 訂閱站台

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.

輸入說明：

The first line of the input file always contains one integer K indicating the
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 ≦　2²⁰ =
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

提示：

出處：

NCPC2011 (管理：morris1028)

作法 : 數學
我不會推導，但是我猜出來了
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;
}

我要檢舉

#a258#NCPC2011#Problem F#Inverse Affine Transform

台長： Morris

您可能對以下文章有興趣

b067. 6. 下棋問題

a250. NCPC2011 Problem H Special Subsequences

[ZJ][spfa、尤拉路徑、bitmask] a416. 6. 城市馬拉松

[ZJ][Math] a348. 1. 貪食蛇

人氣(513) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: 資訊競賽 |
此分類下一篇:a257. NCPC2011 Problem K Key Persons
此分類上一篇:a250. NCPC2011 Problem H Special Subsequences

回應(0)