UVALive - 4270 Discrete Square Roots (扩展欧几里得)
2024-09-02 23:39:54
给出一组正整数$x,n,r$,使得$r^2\equiv x(mod\: n)$,求出所有满足该等式的$r$。
假设有另一个解$r'$满足条件,则有$r^2-r'^2=kn$
因式分解,得$(r+r')(r-r')=kn$
将$n$分解成$a*b$,则有$\left\{\begin{matrix}r+r'=xa\\ r-r'=yb\end{matrix}\right.$
两式相加得$2r=xa+yb$,这是一个二元线性不定方程,可用扩欧求出x的通解。
假设已经求出了$x$的通解$x=x_{0}+k\Delta x$,
由于$r+r'=xa$,所以$r'=xa-r=(x_{0}+k\Delta x)a-r=x_{0}a-r+k(a\Delta x)$,
设$\Delta t=a\Delta x$,则$r'_{0}=((x_{0}a-r)\%\Delta t+\Delta t)\%\Delta t$为$r'$的第一个非负整数解
因此$r'$的通解为$r'=r'_{0}+k\Delta t$
枚举所有的$a,b$,将所有$r'$的可行解插入一个集合里就行了。
#include<bits/stdc++.h> using namespace std;
typedef long long ll;
ll x,n,r,ka;
set<ll> st;
void exgcd(ll a,ll b,ll& x,ll& y,ll& g) {
if(!b)x=,y=,g=a;
else exgcd(b,a%b,y,x,g),y-=x*(a/b);
} void solve(ll a,ll b) {
ll c=*r,x,y,g;
exgcd(a,b,x,y,g);
if(c%g)return;
x*=c/g;
ll dx=abs(b/g);
ll dt=dx*a;
ll t=((a*x-r)%dt+dt)%dt;
for(; t<n; t+=dt)st.insert(t);
} int main() {
while(scanf("%lld%lld%lld",&x,&n,&r)&&x) {
st.clear();
for(ll i=; i*i<=n; ++i)if(n%i==)solve(i,n/i),solve(n/i,i);
printf("Case %lld:",++ka);
for(ll i:st)printf(" %lld",i);
printf("\n");
}
return ;
}
最新文章
- NGUI Atlas Maker sprites with black line issue
- 泛函编程(27)-泛函编程模式-Monad Transformer
- 刀锋上前行!绕过Ramint蠕虫病毒直接脱壳
- Web前端之html_day2
- servlet web文件上传
- 剑指Offer:二进制中1的个数
- [一位菜鸟的COCOS-2D编程之路]打飞机中机种敌机和战机损毁时的爆炸效果
- JQuery轻量级网页编辑器 选中即可编辑
- html中opacity的使用
- 关于智普 - 千人免费学|Python培训|国内最权威python培训|html5
- 使用pfile 启动oracle 实例时,启动失败---db_recovery_file_dest參数值在os上不存在。
- java 企业网站源码模版 有前后台 springmvc SSM 生成静态化
- Jquery.Linq用法
- mitm6:通过IPv6攻破IPv4网络
- [Python爬虫] Selenium爬取新浪微博客户端用户信息、热点话题及评论 (上)
- Self Host 使用 Exceptionless 实时监控程序运行日志服务
- 慕学在线网0.5_xadmin的全局配置
- CentOS查看版本及架构信息
- 08. pt-find
- Ckeditor失去焦点前保留光标位置