Acwing 1301. C 循环 扩展欧几里得算法
内容导读
互联网集市收集整理的这篇技术教程文章主要介绍了Acwing 1301. C 循环 扩展欧几里得算法，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含1177字，纯文字阅读大概需要2分钟。
内容图文
对于 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
a + n * c- (1 << k ) * m = b
a+n?c?(1<<k)?m=b
n
?
c
?
(
1
<
<
k
)
?
m
=
b
?
a
n * c- (1 << k ) * m = b - a
n?c?(1<<k)?m=b?a
a
x
+
b
y
=
g
c
d
(
a
,
b
)
ax+by=gcd(a,b)
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;
}
else
puts("FOREVER");
}
}
内容总结
以上是互联网集市为您收集整理的Acwing 1301. C 循环 扩展欧几里得算法全部内容，希望文章能够帮你解决Acwing 1301. C 循环 扩展欧几里得算法所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。
内容备注
版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。
内容手机端
扫描二维码推送至手机访问。