2018.12.17 bzoj1406 : [AHOI2007]密码箱(简单数论)
2024-10-19 11:49:24
传送门
简单数论暴力题。
题目简述:要求求出所有满足x2≡1mod  nx^2\equiv1 \mod nx2≡1modn且0≤x<n0\le x<n0≤x<n的xxx
考虑到使用平方差公式变形。
(x−1)(x+1)≡0mod  n(x-1)(x+1)\equiv0 \mod n(x−1)(x+1)≡0modn
即(x−1)(x+1)=kn(x-1)(x+1)=kn(x−1)(x+1)=kn
然后就可以枚举nnn大于sqrtnsqrt_nsqrtn的约数ddd来求出可能的xxx。
由上面的式子知道d∣x−1d|x-1d∣x−1或者d∣x+1d|x+1d∣x+1因此就很好判断了。
代码:
#include<bits/stdc++.h>
#define ri register int
using namespace std;
int n,tot;
vector<int>ans,stk;
int main(){
scanf("%d",&n);
for(ri i=1;i*i<=n;++i)if(n%i==0)stk.push_back(n/i);
for(ri i=stk.size()-1;~i;--i){
int d=stk[i];
for(ri j=d;j<=n;j+=d){
if((j-2)%(n/d)==0)ans.push_back(j-1);
if((j+2)%(n/d)==0)ans.push_back(j+1);
}
}
sort(ans.begin(),ans.end()),tot=unique(ans.begin(),ans.end())-ans.begin()-1;
puts("1");
for(ri i=0;i<tot;++i)cout<<ans[i]<<'\n';
return 0;
}
最新文章
- 关于《selenium2自动测试实战--基于Python语言》
- PHP面向对象的一些深入理解
- JAVA集合学习
- [转]分布式文件系统FastDFS架构剖析
- asp.net 后台 修改 javascript 变量
- Python:运算符
- MFC界面开发(QQ透明皮肤:多层算法,一键适配各种背景 )
- JVM线程安全
- python之12306自动查票
- 多路分支----switch语句
- mac终端代理
- UNIX口令破解机
- 【XSY2750】Mythological V 2-sat
- numpy 随机产生数字
- LeetCode--No.005 Longest Palindromic Substring
- canvas使用1
- 每天一个linux命令-用户之间切换
- Visual Studio Code 配置 gcc
- XShell安装
- 【bzoj1502】月下柠檬树