http://acm.timus.ru/problem.aspx?space=1&num=1132
题意:
求 x^2 ≡ n mod p p是质数 的 解
本题中n>=1
特判p=2,接下来求当p是奇素数时的解
引理1:
引理2:方程有解当且仅当
定理:
设a满足 不是模p的二次剩余,
即无解,
那么是二次剩余方程的解
#include<cstdio>
#include<cstdlib>
#include<algorithm> using namespace std; typedef long long LL; int w; struct T
{
int p,d;
}; int mod(LL a,int p)
{
a%=p;
if(a<) a+=p;
return a;
} int Pow(int a,int b,int p)
{
int res=;
for(;b;a=1LL*a*a%p,b>>=)
if(b&) res=1LL*res*a%p;
return res;
} //求勒让德符号
int Legendre(int a,int p)
{
return Pow(a,p->>,p);
} //二次域上的乘法
T mul(T a,T b,int p)
{
T ans;
ans.p=(1LL*a.p*b.p%p+1LL*a.d*b.d%p*w%p)%p;
ans.d=(1LL*a.p*b.d%p+1LL*a.d*b.p%p)%p;
return ans;
} //二次域上的快速幂
T power(T a,int b,int p)
{
T ans;
ans.p=;
ans.d=;
for(;b;a=mul(a,a,p),b>>=)
if(b&) ans=mul(ans,a,p);
return ans;
} int solve(int n,int p)
{
if(p==) return ;
if(Legendre(n,p)+==p) return -;
int a;
LL t;
while()
{
a=rand()%p;
t=1LL*a*a-n;
w=mod(t,p);
if(Legendre(w,p)+==p) break;
}
T tmp;
tmp.p=a;
tmp.d=;
T ans=power(tmp,p+>>,p);
return ans.p;
} int main()
{
int t;
scanf("%d",&t);
int n,p;
int a,b;
while(t--)
{
scanf("%d%d",&n,&p);
n%=p;
a=solve(n,p);
if(a==-)
{
puts("No root");
continue;
}
b=p-a;
if(a>b) swap(a,b);
if(a==b) printf("%d\n",a);
else printf("%d %d\n",a,b);
}
}
Timus 1132 Square Root(二次剩余)的更多相关文章
-
Timus 1132 Square Root(二次剩余 解法2)
不理解,背板子 #include<cstdio> using namespace std; int Pow(int a,int b,int p) { ; ) ) res=1LL*a*res ...
-
URAL 1132 Square Root(二次剩余定理)题解
题意: 求\(x^2 \equiv a \mod p\) 的所有整数解 思路: 二次剩余定理求解. 参考: 二次剩余Cipolla's algorithm学习笔记 板子: //二次剩余,p是奇质数 l ...
-
Codeforces 715A. Plus and Square Root[数学构造]
A. Plus and Square Root time limit per test 2 seconds memory limit per test 256 megabytes input stan ...
-
Project Euler 80:Square root digital expansion 平方根数字展开
Square root digital expansion It is well known that if the square root of a natural number is not an ...
-
Codeforces 612E - Square Root of Permutation
E. Square Root of Permutation A permutation of length n is an array containing each integer from 1 t ...
-
Codeforces 715A &; 716C Plus and Square Root【数学规律】 (Codeforces Round #372 (Div. 2))
C. Plus and Square Root time limit per test 2 seconds memory limit per test 256 megabytes input stan ...
-
(Problem 57)Square root convergents
It is possible to show that the square root of two can be expressed as an infinite continued fractio ...
-
Square Root
Square RootWhen the square root functional configuration is selected, a simplified CORDIC algorithm ...
-
Codeforces Round #372 (Div. 1) A. Plus and Square Root 数学题
A. Plus and Square Root 题目连接: http://codeforces.com/contest/715/problem/A Description ZS the Coder i ...
随机推荐
-
Java中 static/transient,final/volatile 说明
你可以任意使用如下的修改限定关键字来定义一个字段:final或者volatile和/或者static和/或者transient. 如果你将一个字段定义为final,编译器将确保字段当成一个常量——只读 ...
-
Tencent 的电话面试
Tencent的实习生招聘投了简历.然后,万万没想到昨晚腾讯IEG直接给我电话了.当时就惊呆了,我都没有找人内推,就直接电话面试了. 就为昨晚的电话面试写写感想吧!问的挺多的,基本上简历上写了的都问到 ...
-
Android SDK +Eclipse+ADT+CDT+NDK 开发环境在windows 7下的搭建
Android SDK+Eclipse+ADT+CDT+NDK 开发环境在windows 7下的搭建 这几天一直在研究 Android SDK C/C++平台的搭建,尽管以前有成功在Windows ...
-
python解惑之 __file__ 与argv[0]
在python下,获取当前执行主脚本的方法有两个:sys.argv[0]和__file__. sys.argv[0] 获取主执行文件路径的最佳方法是用sys.argv[0],它可能是一个相对路径,所以 ...
-
分享几个 git 的使用场景
你真的会使用 git 吗?你能回答下面几个问题吗? 有三个commit(顺序:CommitA.CommitB.CommitC),它们相互独立,没有依赖. 在不修改B.C的前提下,修改A,怎么操作? 合 ...
-
【noip模拟赛1】古韵之乞巧 (dp)
描述 闺女求天女,更阑意未阑. 玉庭开粉席,罗袖捧金盘. 向月穿针易,临风整线难. 不知谁得巧,明旦试相看. ——祖咏<七夕> 女子乞巧,是七夕的重头戏.古时,女子擅长女红被视为一种重要的 ...
-
Cocoa 集合类型:NSPointerArray,NSMapTable,NSHashTable
iOS 中有很多种集合类型,最为常见的可能就 NSArray.NSDictionary.NSSet,但其实还有 NSPointerArray.NSMapTable.NSHashTable 等类型,虽然 ...
-
iOS NSURLConnection使用详解
一.整体介绍 NSURLConnection是苹果提供的原生网络访问类,但是苹果很快会将其废弃,且由NSURLSession(iOS7以后)来替代.目前使用最广泛的第三方网络框架AFNetworkin ...
-
撩课-Java每天5道面试题第15天
撩课Java+系统架构点击开始学习 106.什么是Hibernate的并发机制?怎么去处理并发问题? a.Hibernate的Session对象是非线程安全的, 对于单个请求,单个会话, 单个的工作单 ...
-
用 Qt 的 QAudioOutput 类播放 WAV 音频文件
用 Qt 的 QAudioOutput 类播放 WAV 音频文件 最近有一个项目,需要同时控制 4 个声卡播放不同的声音,声音文件很简单就是没有任何压缩的 wav 文件. 如果只是播放 wav 文件, ...