HDU5478 Can you find it 数学快速幂

本文主要是介绍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 pint 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;}

 

这篇关于HDU5478 Can you find it 数学快速幂的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---