Acwing 1301. C 循环 扩展欧几里得算法

Acwing 1301. C 循环

对于 C 语言的循环语句，形如：

for (variable = A; variable != B; variable += C)
statement;
请问在 k 位存储系统中循环几次才会结束。

若在有限次内结束，则输出循环次数。否则输出死循环。

输入格式
多组数据，每组数据一行四个整数 A,B,C,k。

读入以 0 0 0 0 结束。

输出格式
若在有限次内结束，则输出循环次数。

否则输出 FOREVER。

数据范围
1≤k≤32,
0≤A,B,C<2k
输入样例：

3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0

输出样例：

0
2
32766
FOREVER

这道题很明显就是一个欧几里得算法的一个变形。

这是算法的一个变形

$$a+n?c?(1<<k)?m=b$$
$$n?c?(1<<k)?m=b?a$$
$$ax+by=gcd(a,b)$$
然后使用扩展欧几里得算法，去把 c,(1<<k)作为扩展欧几里得的a和b,然后去求n，m

做这道题的固定套路是对m除以k，然后用类似于求哈希函数一样，最后输出答案

代码如下。

#include<iostream>using namespace std;typedef long long LL;LL exgcd(LL a,LL b,LL &x,LL &y)
{
    if(!b){
    x=1;y=0;return a;}LL d=exgcd(b,a%b,y,x);y-=a/b*x;return d;
}int main(void)
{
    LL a,b,c,k;while(cin>>a>>b>>c>>k,a||b||c||k){
    k=(LL)1<<k;LL n,m;LL  d=exgcd(c,k,n,m);if((b-a)%d==0){
    n*=(b-a)/d;LL z=k/d;cout<<(n%z+z)%z<<endl;}elseputs("FOREVER");}
}