Can you find it
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Problem Description
Given a prime number
C(1≤C≤2×105) , and three integers k1, b1, k2
(1≤k1,k2,b1≤109) . Please find all pairs (a, b) which satisfied the equation
ak1?n+b1 +
bk2?n?k2+1 = 0 (mod C)(n = 1, 2, 3, ...).
Input
There are multiple test cases (no more than 30). For each test, a single line contains four integers C, k1, b1, k2.
Output
First, please output "Case #k: ", k is the number of test case. See sample output for more detail.
Please output all pairs (a, b) in lexicographical order. (1≤a,b<C) . If there is not a pair (a, b), please output -1.
Please output all pairs (a, b) in lexicographical order. (1≤a,b<C) . If there is not a pair (a, b), please output -1.
Sample Input
23 1 1 2
Sample Output
Case #1: 1 22
Source
2015 ACM/ICPC Asia Regional Shanghai Online
题意：给你C,k1,k2,b1，按字典序输出满足
解题思路：因为
而n=2的情况也是符合的，可得
因为①式mod C = 0 ,所以①式乘以一个数mod C 仍为0，不妨①式*
所以，我们只需遍历一遍a的取值(1~C-1)，利用快速幂计算出
#pragma comment(linker, "/STACK:1024000000,1024000000")
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<queue>
#include<stack>
#include<math.h>
#include<vector>
#include<map>
#include<set>
#include<stdlib.h>
#include<cmath>
#include<string>
#include<algorithm>
#include<iostream>
#define exp 1e-10
using namespace std;
const int N = 200001;
const int inf = 1000000000;
const int mod = 2009;
__int64 Quick_Mod(int a, int b, int m)
{__int64 res = 1,term = a % m;while(b){if(b & 1) res = (res * term) % m;term = (term * term) % m;b >>= 1;}return res%m;
}
int main()
{int C,k1,b1,k2,i,k=1;__int64 a,b,s;bool flag;while(~scanf("%d%d%d%d",&C,&k1,&b1,&k2)){flag=false;printf("Case #%d:\n",k++);for(i=1;i<C;i++){a=Quick_Mod(i,k1,C);b=C-Quick_Mod(i,k1+b1,C);s=Quick_Mod(b,k2,C);//printf("##%I64d %I64d\n",a,s);if(a==s)flag=true,printf("%d %I64d\n",i,b);}if(!flag)puts("-1");}return 0;
}