POJ2115 C Looooops 模线性方程(扩展欧几里得)

时间:2021-07-15 00:44:33

题意:很明显,我就不说了

分析:令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 模线性方程(扩展欧几里得)的更多相关文章

  1. POJ2115 C Looooops ——模线性方程(扩展gcd)

    题目链接:http://poj.org/problem?id=2115 C Looooops Time Limit: 1000MS   Memory Limit: 65536K Total Submi ...

  2. C Looooops&lpar;扩展欧几里得&plus;模线性方程&rpar;

    http://poj.org/problem?id=2115 题意:给出A,B,C和k(k表示变量是在k位机下的无符号整数),判断循环次数,不能终止输出"FOREVER". 即转化 ...

  3. POJ2115 - C Looooops(扩展欧几里得)

    题目大意 求同余方程Cx≡B-A(2^k)的最小正整数解 题解 可以转化为Cx-(2^k)y=B-A,然后用扩展欧几里得解出即可... 代码: #include <iostream> us ...

  4. 【扩展欧几里得】poj2115 C Looooops

    题意大概是让你求(A+Cx) mod 2^k = B的最小非负整数解. 若(B-A) mod gcd(C,2^k) = 0,就有解,否则无解. 式子可以化成Cx + 2^k*y = B - A,可以用 ...

  5. poj2115 C Looooops——扩展欧几里得

    题目:http://poj.org/problem?id=2115 就是扩展欧几里得呗: 然而忘记除公约数... 代码如下: #include<iostream> #include< ...

  6. POJ1061&colon;青蛙的约会&plus;POJ2115C Looooops&plus;UVA10673Play with Floor and Ceil(扩展欧几里得)

    http://poj.org/problem?id=1061 第一遍的写法: #include <iostream> #include <stdio.h> #include & ...

  7. POJ2115&lpar;扩展欧几里得&rpar;

    C Looooops Time Limit: 1000MS   Memory Limit: 65536K Total Submissions: 23700   Accepted: 6550 Descr ...

  8. URAL 1141&period; RSA Attack(欧拉定理&plus;扩展欧几里得&plus;快速幂模)

    题目链接 题意 : 给你n,e,c,并且知道me ≡ c (mod n),而且n = p*q,pq都为素数. 思路 : 这道题的确与题目名字很相符,是个RSA算法,目前地球上最重要的加密算法.RSA算 ...

  9. 浅谈扩展欧几里得&lbrack;exgcd&rsqb; By cellur925

    关于扩展欧几里得从寒假时就很迷,抄题解过了同余方程,但是原理并不理解. 今天终于把坑填上了qwq. 由于本人太菜,不会用markdown,所以这篇总结是手写的(什么).(字丑不要嫌弃嘛) ****** ...

随机推荐

  1. 解析 Json 相关

    statusJson sj = new statusJson() { ShipmentNum = "555555", Status1 = "05", Wareh ...

  2. 注解的基本盘点 -- 《Java编程思想》

    注解(元数据)为我们在代码中添加信息提供了一种形式化的方法,使我们可以在之后的某一个时刻非常方便地使用这些数据. ---<Java编程思想> 其实注解可以理解为一个工具类,只要使用了这个工 ...

  3. UWP&sol;Win10新特性系列—UserConsentVerifier

    在UWP开发中,微软提供了新的用户许可验证方式-指纹(生物识别).Pin.密码验证.在爆料的新型Win10 Mobile移动设备中,会增加虹膜识别等先进的用户身份识别技术,微软现在统一了身份验证的AP ...

  4. ViewPager—01引导页的制作

    布局文件 <RelativeLayout xmlns:android="http://schemas.android.com/apk/res/android" xmlns:t ...

  5. 【Android Studio安装部署系列】五、新建你的第一个项目:HelloWorld

    版权声明:本文为HaiyuKing原创文章,转载请注明出处! 概述 新建项目的步骤. 开始创建项目 如果是刚安装Android studio的话,点击Start a new Android Studi ...

  6. 怎么给easyui中的datagrid加水平滚动条

    注意如下几个点就行: 1.数据网格(DataGrid)所在的table属性上级div无需设置width: 2..datagrid属性:fitColumns为false 或者不填 3.在style中给. ...

  7. elasticsearch系列八:ES 集群管理(集群规划、集群搭建、集群管理)

    一.集群规划 搭建一个集群我们需要考虑如下几个问题: 1. 我们需要多大规模的集群? 2. 集群中的节点角色如何分配? 3. 如何避免脑裂问题? 4. 索引应该设置多少个分片? 5. 分片应该设置几个 ...

  8. JS学习笔记9&lowbar;JSON

    1.JSON概述 JavaScript Object Natation,js对象表示法,(像XML一样)是一种数据格式,它与js有相同的语法形式 P.S.一点小历史:JSON之父是道格拉斯,<J ...

  9. BZOJ4919 大根堆(动态规划&plus;treap&plus;启发式合并)

    一个显然的dp是设f[i][j]为i子树内权值<=j时的答案,则f[i][j]=Σf[son][j],f[i][a[i]]++,f[i][a[i]+1~n]对其取max.这样是可以线段树合并的, ...

  10. jQ&amp&semi;js给label

    <strong>当前角色:</strong><label id="lblRoleName" style="margin-bottom: 0p ...