HDU5478 Can you find it 数学快速幂

Given a prime number C(1≤C≤2×105)C(1≤C≤2×105), and three integers k1, b1, k2 (1≤k1,k2,b1≤109)(1≤k1,k2,b1≤109). Please find all pairs (a, b) which satisfied the equation ak1⋅n+b1ak1⋅n+b1 + bk2⋅n−k2+1bk2⋅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)(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

题意：

        略

分析：

代码：

#include<cstdio>
#include<utility>
#include<algorithm>
#include<cstring>
#include<iostream>
using namespace std;
int c,k1,b1,k2,time,flag;
int qic_mod(int a, int b, int p) { /// calculate (a ^ b) mod p
	int ans = 1 % p;
	for (; b; b >>= 1)
    {
		if (b & 1) ans = (long long)ans * a % p;
		a = (long long)a * a % p;
	}
	return ans;
}
int main()
{
    while(scanf("%d",&c)!=EOF)
    {
        scanf("%d%d%d",&k1,&b1,&k2);
        printf("Case #%d:\n",++time);
        flag=0;
        for(int a=1;a<c;a++)
        {
            int right=qic_mod(a,k1,c);
            int b=c-qic_mod(a,k1+b1,c);
            int left=qic_mod(b,k2,c);
            if(right==left)
            {
                printf("%d% d\n",a,b);
                flag=1;
            }
        }
         if(!flag) printf("-1\n");
    }
       return 0;

}