POJ 2115 C Looooops（exgcd）

r囧r小猫 2023-06-04 13:57 36阅读 0赞

嗯...

题目链接：http://poj.org/problem?id=2115

(A+s\*C)%2^k=B

(A+s\*C)≡B(mod 2^k)

s\*C-m\*2^k=B-A

ax+by=c

有一个问题，b没必要是负的，反正正负a和b的线性组合集都一样，况且此题不需要y

AC代码：

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include<cstdio>
     2 #include<iostream>
     3 
     4 using namespace std;
     5 
     6 inline void exgcd(long long a, long long b, long long &g, long long &x, long long &y){
     7     if(!b) { g = a; x = 1; y = 0;}
     8     else { exgcd(b, a % b, g, y, x); y -= x * (a / b);}
     9 }
    10 
    11 int main(){
    12     long long a, b, c, A, B, C, k, g, x, y;
    13     while(~scanf("%lld%lld%lld%lld", &A, &B, &C, &k)){
    14         if(!A && !B && !C && !k) break;
    15         a = C; b = 1ll << k; c = B - A;
    16         exgcd(a, b, g, x, y);
    17         if(c % g) printf("FOREVER\n");
    18         else{
    19             c /= g; b /= g;
    20             printf("%lld\n", (x % b * c % b + b) % b);
    21         }
    22     }
    23     return 0;
    24 }

AC代码

转载于:https://www.cnblogs.com/New-ljx/p/11515341.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c747b1a8f1f542e287d5c868e29f30c1.png

发表评论取消回复

表情：

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

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

相关阅读

相关 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 赞/ 37 阅读

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

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

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

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

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

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

相关 Sumsets poj 2229 c++

Sumsets <table> <tbody> <tr> <td><strong>Time Limit:</strong> 2000MS</td>

刺骨的言语ヽ痛彻心扉/ 2022年08月10日 16:37/ 0 赞/ 57 阅读

相关 Palindrome poj 1159 c++

Palindrome <table> <tbody> <tr> <td><strong>Time Limit:</strong> 3000MS</td>

矫情吗；*/ 2022年08月10日 16:36/ 0 赞/ 8 阅读

相关 Costume Party poj 3663 c++

Costume Party <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

超、凢脫俗/ 2022年08月10日 16:35/ 0 赞/ 134 阅读

相关 Tree Recovery poj 2255 c++

Tree Recovery <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000M

墨蓝/ 2022年08月10日 13:50/ 0 赞/ 26 阅读

相关 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 阅读

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

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

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

相关 poj 2115

Compiler Mystery: We are given a C-language style for loop of type for (variable

逃离我推掉我的手/ 2021年11月02日 01:24/ 0 赞/ 191 阅读