首页 > 代码库 > HDU5478(快速幂)
HDU5478(快速幂)
Can you find it
Time Limit: 8000/5000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1407 Accepted Submission(s): 581
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
思路:枚举a。当n=1时,ak1+b+b=0(mod C),则b=C-ak1+b(mod C)。再利用n=2,验证b是否正确。
#include <cstdio>using namespace std;typedef long long LL;LL C,k1,b1,k2;LL npow(LL x,LL n,LL mod){ LL res=1; while(n>0) { if(n&1) res=(res*x)%mod; x=(x*x)%mod; n>>=1; } return res;}int main(){ int cas=0; while(scanf("%lld%lld%lld%lld",&C,&k1,&b1,&k2)!=EOF) { bool tag=false; printf("Case #%d:\n",++cas); for(LL a=1;a<C;a++) { LL b=C-npow(a,k1+b1,C); LL x=npow(a,2*k1+b1,C); LL y=npow(b,k2+1,C); if((x+y)%C==0) { tag=true; printf("%lld %lld\n",a,b); } } if(!tag) { printf("-1\n"); } } return 0;}
HDU5478(快速幂)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。