C Looooops

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 1093 字

k位无符号系统中循环for，求最小非负循环次

一本通
练习

正文

/*
原题：「一本通 6.4 练习 4」C Looooops（CTU Open 2004）
题意：k 位无符号系统中循环 for(v=A; v!=B; v+=C)，求最小非负循环次数 x；若永不结束输出 FOREVER。
思路：等价于 (A + C·x) ≡ B (mod 2^k)，即 C·x ≡ (B-A) (mod 2^k)；用扩展欧几里得求该线性同余最小非负解，无解则 FOREVER。
复杂度：O(log 2^k) 每组。
易错点：模为 2^k 用 1LL<<k 计算（k≤32 不会溢出）；最终乘积用 __int128 防溢出；gcd(C,2^k) 不整除 (B-A) 时输出 FOREVER；读入 0 0 0 0 结束。
*/
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
ll exgcd(ll a,ll b,ll &x,ll &y){
    if(b==0){
        x=1;y=0;
        return a;
    }
    ll x1,y1;
    ll g=exgcd(b,a%b,x1,y1);
    x=y1;
    y=x1-(a/b)*y1;
    return g;
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll A,B,C,k;
    while(cin>>A>>B>>C>>k){
        if(A==0&&B==0&&C==0&&k==0)break;
        ll mod=1LL<<k;                 // 2^k
        ll b=(B-A)%mod;
        if(b<0)b+=mod;                 // C·x ≡ b (mod mod)
        ll x,u;
        ll g=exgcd(C,mod,x,u);
        if(b%g!=0){
            cout<<"FOREVER\n";
            continue;
        }
        ll mg=mod/g;
        x=((x%mg)+mg)%mg;
        x=(__int128)x*(b/g)%mg;
        cout<<x<<'\n';
    }
    return 0;
}

C Looooops

正文

一本通·提高篇的其它内容