poj 2115 C Looooops 扩展欧几里德
2024-08-29 12:22:19
C Looooops
Time Limit: 1000MS | Memory Limit: 65536K | |
Total Submissions: 23616 | Accepted: 6517 |
Description
A Compiler Mystery: We are given a C-language style for loop of type
for (variable = A; variable != B; variable += C)
statement;
I.e., a loop which starts by setting variable to value A and while variable is not equal to B, repeats statement followed by increasing the variable by C. We want to know how many times does the statement get executed for particular values of A, B and C, assuming that all arithmetics is calculated in a k-bit unsigned integer type (with values 0 <= x < 2k) modulo 2k.
Input
The input consists of several instances. Each instance is described by a single line with four integers A, B, C, k separated by a single space. The integer k (1 <= k <= 32) is the number of bits of the control variable of the loop and A, B, C (0 <= A, B, C < 2k) are the parameters of the loop.
The input is finished by a line containing four zeros.
Output
The output consists of several lines corresponding to the instances on the input. The i-th line contains either the number of executions of the statement in the i-th instance (a single integer number) or the word FOREVER if the loop does not terminate.
Sample Input
3 3 2 16
3 7 2 16
7 3 2 16
3 4 2 16
0 0 0 0
Sample Output
0
2
32766
FOREVER
Source
题意:(a+bx)%(2^k)==c,求x最小值;
思路:解扩展欧几里德;
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
#define ll long long
#define esp 1e-13
const int N=1e4+,M=1e6+,inf=1e9+,mod=;
void extend_Euclid(ll a, ll b, ll &x, ll &y)
{
if(b == )
{
x = ;
y = ;
return;
}
extend_Euclid(b, a % b, x, y);
ll tmp = x;
x = y;
y = tmp - (a / b) * y;
}
ll gcd(ll a,ll b)
{
if(b==)
return a;
return gcd(b,a%b);
}
ll pow1(ll x)
{
ll sum=;
for(ll i=;i<x;i++)
sum*=;
return sum;
}
int main()
{
ll x,y,i,z,t;
while(~scanf("%lld%lld%lld%lld",&x,&y,&i,&t))
{
if(x==&&y==&&i==&&t==)
break;
ll m=pow1(t);
ll c=((y-x)%m+m)%m;
ll j,k;
if(c%gcd(m,i)==)
{
extend_Euclid(i,m,j,k);
ll ans=j*(c/gcd(m,i));
m=m/gcd(m,i);
printf("%lld\n",(ans%m+m)%m);
}
else
printf("FOREVER\n");
}
return ;
}
最新文章
- Erlang 从入门到精通(一) 下载安装
- ASP.NET中使用DropDownList实现无刷新二级联动详细过程
- egrep 查找IP
- toast 防止一直不停弹出,累积显示
- 根据子查询批量删除的sql语句
- Context上下文
- 快学Scala-第九章 文件和正则表达式
- 使用JAXP进行XM解析(基于DOM)
- Bootloader Project
- 面试题:JQuery有几种选择器?
- TensorFlow从1到2(二)续讲从锅炉工到AI专家
- JQuery 目录树jsTree插件用法
- GDAL对TIF创建内建金字塔一个问题
- 物体检测算法 SSD 的训练和测试
- 皮尔逊残差 | Pearson residual
- 第6章 静态路由和动态路由(3)_RIP动态路由协议
- iOS app bundle id
- 使用GitHub管理代码
- SAP请求号的传输
- 由于防火墙限制无法访问linux服务器上的tomcat应用