pku 2115 C Looooops 同余定理

- 日理万妓 2022-08-04 15:53 180阅读 0赞

\#include <stdio.h> long long mod(long long a,long long b) \{ return (a % b + b) % b; \} struct triple \{ long long d,x,y; \}; long long Euclid(long long a,long long b) \{ if(b == 0) return a; else return Euclid(b,mod(a,b)); \} triple Extended\_Euclid(long long a,long long b) \{ triple result; if(b == 0) \{ result.d = a; result.x = 1; result.y = 0; \} else \{ triple ee = Extended\_Euclid(b,mod(a,b)); result.d = ee.d; result.x = ee.y; result.y = ee.x - (a/b)\*ee.y; \} return result; \} long long MLES(long long a,long long b,long long n) \{ triple ee = Extended\_Euclid(a,n); if(mod(b,ee.d) == 0) return mod((ee.x \* (b / ee.d)),n/ee.d); else return -1; \} int main() \{ long long A, B, C, k; while(scanf("%I64d%I64d%I64d%I64d", &A, &B, &C, &k) && !(A==0&&B==0&&C==0&&k==0)) \{ if(A == B) \{ printf("0/n"); continue; \} long long ret = MLES(C, B-A, ((long long)1)<<k); //((long long)1)<<k //这儿要注意,1<<32位后,会超过int的最大值,需要转换为long long if(ret == -1) printf("FOREVER/n"); else printf("%I64d/n", ret); \} return 0; \}

发表评论取消回复

表情：

评论列表（有 0 条评论，180人围观）

还没有评论，来说两句吧...

相关阅读

相关 POJ 2115 C Looooops（exgcd）

嗯... 题目链接：http://poj.org/problem?id=2115 (A+s\C)%2^k=B (A+s\C)≡B(mod 2^k) s\C-

r囧r小猫/ 2023年06月04日 13:57/ 0 赞/ 36 阅读

相关 Poj 2115 C Looooops (模线性方程)

题意：对于循环语句for(i=A ; i!=B ;i +=C)，问在无符号的k位存储系统中循环几次才会结束。若在有限次内结束，则输出循环次数，否则输出死循环。思路：例如k=

待我称王封你为后i/ 2022年09月17日 07:29/ 0 赞/ 35 阅读

相关 POJ 2115-C Looooops-扩展欧几里德算法

C Looooops <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

╰半橙微兮°/ 2022年08月21日 01:12/ 0 赞/ 183 阅读

相关同余模定理

同余模定理定义： • 所谓的同余，顾名思义，就是许多的数被一个数d去除，有相同的余数。d数学上的称谓为模。如a=6,b=1,d=5,则我们说a和b是模d同余的。因为他

谁借莪１个温暖的怀抱￠/ 2022年08月21日 00:19/ 0 赞/ 208 阅读

相关 pku 2115 C Looooops 同余定理

\include <stdio.h> long long mod(long long a,long long b) \{ return (a % b + b) % b; \}

- 日理万妓/ 2022年08月04日 15:53/ 0 赞/ 181 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

左手的ㄟ右手/ 2022年07月15日 11:29/ 0 赞/ 224 阅读

相关同余定理（求余数）

现在给你一个自然数n，它的位数小于等于一百万，现在你要做的就是求出这个数除10003之后的余数输入第一行有一个整数m(1<=m<=8),表示有m组测试数

Bertha 。/ 2022年07月15日 11:29/ 0 赞/ 236 阅读

相关同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均为正整数

悠悠/ 2022年06月17日 08:29/ 0 赞/ 244 阅读

相关【转载】--同余定理

同余运算及其基本性质 100除以7的余数是2，意思就是说把100个东西七个七个分成一组的话最后还剩2个。余数有一个严格的定义：假如被除数是a，除数是b（假设它们均

矫情吗；*/ 2022年06月10日 12:28/ 0 赞/ 970 阅读

相关 POJ2115 C Looooops(拓展欧几里德)

题意：要求a不断加c到达b，如果a大于2^k就mod2^k，求最少要加几次c。要点：拓展欧几里德算法求最小整数解，就是个模板。不过要注意计算2^k时因为超出int范

墨蓝/ 2021年12月20日 23:11/ 0 赞/ 215 阅读