题意:很明显,我就不说了
分析:令n=2^k,因为A,B,C<n,所以取模以后不会变化,所以就是求(A+x*C)%n=B
转化一下就是求 C*x=B-A(%n),最小的x
令a=C,b=B-A
原式等于ax=b(mod n) 这就是标准的解模线性方程
该方程有解的充要条件是d=gcd(n,a) && d|b(可以根据这一条判断是否FOREVER)
然后参考算法导论应用扩展欧几里得求解x
a*x0+n*y0=d
x=x0*(b/d)(mod n)
然后应用多解条件求最小正整数解,即解的最小间距t=n/d,x+=i*t,i=0,1,..d-1
x=(x%t+t)%t
代码:
#include <cstdio>
#include <iostream>
#include <ctime>
#include <vector>
#include <cmath>
#include <map>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long LL;
LL x,y;
LL Egcd(LL a,LL b)
{
if(b==)
{
x=;
y=;
return a;
}
int res=Egcd(b,a%b);
LL tmp=x;
x=y;
y=tmp-a/b*y;
return res;
}
int main()
{
LL a,b,c,k;
while(~scanf("%I64d%I64d%I64d%I64d",&a,&b,&c,&k))
{
if(!a&&!b&&!c&&!k)break;
LL n=(1ll<<k);
LL d=Egcd(c,n);
if((b-a)%d)
{
printf("FOREVER\n");
continue;
}
x*=((b-a)/d);
x=(x%(n/d)+n/d)%(n/d);
printf("%I64d\n",x);
}
return ;
}
POJ2115 C Looooops 模线性方程(扩展欧几里得)的更多相关文章
-
POJ2115 C Looooops ——模线性方程(扩展gcd)
题目链接:http://poj.org/problem?id=2115 C Looooops Time Limit: 1000MS Memory Limit: 65536K Total Submi ...
-
C Looooops(扩展欧几里得+模线性方程)
http://poj.org/problem?id=2115 题意:给出A,B,C和k(k表示变量是在k位机下的无符号整数),判断循环次数,不能终止输出"FOREVER". 即转化 ...
-
POJ2115 - C Looooops(扩展欧几里得)
题目大意 求同余方程Cx≡B-A(2^k)的最小正整数解 题解 可以转化为Cx-(2^k)y=B-A,然后用扩展欧几里得解出即可... 代码: #include <iostream> us ...
-
【扩展欧几里得】poj2115 C Looooops
题意大概是让你求(A+Cx) mod 2^k = B的最小非负整数解. 若(B-A) mod gcd(C,2^k) = 0,就有解,否则无解. 式子可以化成Cx + 2^k*y = B - A,可以用 ...
-
poj2115 C Looooops——扩展欧几里得
题目:http://poj.org/problem?id=2115 就是扩展欧几里得呗: 然而忘记除公约数... 代码如下: #include<iostream> #include< ...
-
POJ1061:青蛙的约会+POJ2115C Looooops+UVA10673Play with Floor and Ceil(扩展欧几里得)
http://poj.org/problem?id=1061 第一遍的写法: #include <iostream> #include <stdio.h> #include & ...
-
POJ2115(扩展欧几里得)
C Looooops Time Limit: 1000MS Memory Limit: 65536K Total Submissions: 23700 Accepted: 6550 Descr ...
-
URAL 1141. RSA Attack(欧拉定理+扩展欧几里得+快速幂模)
题目链接 题意 : 给你n,e,c,并且知道me ≡ c (mod n),而且n = p*q,pq都为素数. 思路 : 这道题的确与题目名字很相符,是个RSA算法,目前地球上最重要的加密算法.RSA算 ...
-
浅谈扩展欧几里得[exgcd] By cellur925
关于扩展欧几里得从寒假时就很迷,抄题解过了同余方程,但是原理并不理解. 今天终于把坑填上了qwq. 由于本人太菜,不会用markdown,所以这篇总结是手写的(什么).(字丑不要嫌弃嘛) ****** ...
随机推荐
-
解析 Json 相关
statusJson sj = new statusJson() { ShipmentNum = "555555", Status1 = "05", Wareh ...
-
注解的基本盘点 -- 《Java编程思想》
注解(元数据)为我们在代码中添加信息提供了一种形式化的方法,使我们可以在之后的某一个时刻非常方便地使用这些数据. ---<Java编程思想> 其实注解可以理解为一个工具类,只要使用了这个工 ...
-
UWP/Win10新特性系列—UserConsentVerifier
在UWP开发中,微软提供了新的用户许可验证方式-指纹(生物识别).Pin.密码验证.在爆料的新型Win10 Mobile移动设备中,会增加虹膜识别等先进的用户身份识别技术,微软现在统一了身份验证的AP ...
-
ViewPager—01引导页的制作
布局文件 <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:t ...
-
【Android Studio安装部署系列】五、新建你的第一个项目:HelloWorld
版权声明:本文为HaiyuKing原创文章,转载请注明出处! 概述 新建项目的步骤. 开始创建项目 如果是刚安装Android studio的话,点击Start a new Android Studi ...
-
怎么给easyui中的datagrid加水平滚动条
注意如下几个点就行: 1.数据网格(DataGrid)所在的table属性上级div无需设置width: 2..datagrid属性:fitColumns为false 或者不填 3.在style中给. ...
-
elasticsearch系列八:ES 集群管理(集群规划、集群搭建、集群管理)
一.集群规划 搭建一个集群我们需要考虑如下几个问题: 1. 我们需要多大规模的集群? 2. 集群中的节点角色如何分配? 3. 如何避免脑裂问题? 4. 索引应该设置多少个分片? 5. 分片应该设置几个 ...
-
JS学习笔记9_JSON
1.JSON概述 JavaScript Object Natation,js对象表示法,(像XML一样)是一种数据格式,它与js有相同的语法形式 P.S.一点小历史:JSON之父是道格拉斯,<J ...
-
BZOJ4919 大根堆(动态规划+treap+启发式合并)
一个显然的dp是设f[i][j]为i子树内权值<=j时的答案,则f[i][j]=Σf[son][j],f[i][a[i]]++,f[i][a[i]+1~n]对其取max.这样是可以线段树合并的, ...
-
jQ&;js给label
<strong>当前角色:</strong><label id="lblRoleName" style="margin-bottom: 0p ...