Timus 1132 Square Root(二次剩余)

时间:2022-11-06 13:16:13

http://acm.timus.ru/problem.aspx?space=1&num=1132

题意:

求 x^2 ≡ n mod p  p是质数 的 解

本题中n>=1

特判p=2,接下来求当p是奇素数时的解

引理1:Timus 1132 Square Root(二次剩余)

引理2:方程有解当且仅当Timus 1132 Square Root(二次剩余)

定理:

设a满足 Timus 1132 Square Root(二次剩余)不是模p的二次剩余,

Timus 1132 Square Root(二次剩余)无解,

那么Timus 1132 Square Root(二次剩余)是二次剩余方程Timus 1132 Square Root(二次剩余)的解

Timus 1132 Square Root(二次剩余)

#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(二次剩余)的更多相关文章

  1. Timus 1132 Square Root&lpar;二次剩余 解法2)

    不理解,背板子 #include<cstdio> using namespace std; int Pow(int a,int b,int p) { ; ) ) res=1LL*a*res ...

  2. URAL 1132 Square Root(二次剩余定理)题解

    题意: 求\(x^2 \equiv a \mod p\) 的所有整数解 思路: 二次剩余定理求解. 参考: 二次剩余Cipolla's algorithm学习笔记 板子: //二次剩余,p是奇质数 l ...

  3. Codeforces 715A&period; Plus and Square Root&lbrack;数学构造&rsqb;

    A. Plus and Square Root time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

  4. 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 ...

  5. 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 ...

  6. Codeforces 715A &amp&semi; 716C Plus and Square Root【数学规律】 &lpar;Codeforces Round &num;372 &lpar;Div&period; 2&rpar;&rpar;

    C. Plus and Square Root time limit per test 2 seconds memory limit per test 256 megabytes input stan ...

  7. (Problem 57)Square root convergents

    It is possible to show that the square root of two can be expressed as an infinite continued fractio ...

  8. Square Root

    Square RootWhen the square root functional configuration is selected, a simplified CORDIC algorithm ...

  9. Codeforces Round &num;372 &lpar;Div&period; 1&rpar; A&period; Plus and Square Root 数学题

    A. Plus and Square Root 题目连接: http://codeforces.com/contest/715/problem/A Description ZS the Coder i ...

随机推荐

  1. Java中 static&sol;transient&comma;final&sol;volatile 说明

    你可以任意使用如下的修改限定关键字来定义一个字段:final或者volatile和/或者static和/或者transient. 如果你将一个字段定义为final,编译器将确保字段当成一个常量——只读 ...

  2. Tencent 的电话面试

    Tencent的实习生招聘投了简历.然后,万万没想到昨晚腾讯IEG直接给我电话了.当时就惊呆了,我都没有找人内推,就直接电话面试了. 就为昨晚的电话面试写写感想吧!问的挺多的,基本上简历上写了的都问到 ...

  3. Android SDK &plus;Eclipse&plus;ADT&plus;CDT&plus;NDK 开发环境在windows 7下的搭建

    Android SDK+Eclipse+ADT+CDT+NDK 开发环境在windows 7下的搭建 这几天一直在研究 Android SDK  C/C++平台的搭建,尽管以前有成功在Windows ...

  4. python解惑之 &lowbar;&lowbar;file&lowbar;&lowbar; 与argv&lbrack;0&rsqb;

    在python下,获取当前执行主脚本的方法有两个:sys.argv[0]和__file__. sys.argv[0] 获取主执行文件路径的最佳方法是用sys.argv[0],它可能是一个相对路径,所以 ...

  5. 分享几个 git 的使用场景

    你真的会使用 git 吗?你能回答下面几个问题吗? 有三个commit(顺序:CommitA.CommitB.CommitC),它们相互独立,没有依赖. 在不修改B.C的前提下,修改A,怎么操作? 合 ...

  6. 【noip模拟赛1】古韵之乞巧 (dp)

    描述 闺女求天女,更阑意未阑. 玉庭开粉席,罗袖捧金盘. 向月穿针易,临风整线难. 不知谁得巧,明旦试相看. ——祖咏<七夕> 女子乞巧,是七夕的重头戏.古时,女子擅长女红被视为一种重要的 ...

  7. Cocoa 集合类型:NSPointerArray,NSMapTable,NSHashTable

    iOS 中有很多种集合类型,最为常见的可能就 NSArray.NSDictionary.NSSet,但其实还有 NSPointerArray.NSMapTable.NSHashTable 等类型,虽然 ...

  8. iOS NSURLConnection使用详解

    一.整体介绍 NSURLConnection是苹果提供的原生网络访问类,但是苹果很快会将其废弃,且由NSURLSession(iOS7以后)来替代.目前使用最广泛的第三方网络框架AFNetworkin ...

  9. 撩课-Java每天5道面试题第15天

    撩课Java+系统架构点击开始学习 106.什么是Hibernate的并发机制?怎么去处理并发问题? a.Hibernate的Session对象是非线程安全的, 对于单个请求,单个会话, 单个的工作单 ...

  10. 用 Qt 的 QAudioOutput 类播放 WAV 音频文件

    用 Qt 的 QAudioOutput 类播放 WAV 音频文件 最近有一个项目,需要同时控制 4 个声卡播放不同的声音,声音文件很简单就是没有任何压缩的 wav 文件. 如果只是播放 wav 文件, ...