【BZOJ】3239: Discrete Logging
2024-10-11 09:15:35
http://www.lydsy.com/JudgeOnline/problem.php?id=3239
题意:原题很清楚了= =
#include <bits/stdc++.h>
using namespace std; map<int, int> s;
typedef long long ll;
int mpow(int a, int b, int p) {
a%=p; int r=1;
while(b) { if(b&1) r=((ll)r*a)%p; a=((ll)a*a)%p; b>>=1; }
return r;
}
void work(int a, int b, int p) {
a%=p; b%=p;
if(b==1) { puts("0"); return; }
if(!a && !b) { puts("1"); return; }
if(!a) { puts("no solution"); return; }
s.clear();
int m=sqrt(p+0.5), t=1, w=a, mm;
for(int i=0; i<m; ++i) s[((ll)b*t)%p]=i, t=((ll)t*w)%p;
w=mpow(a, m, p); t=1; mm=(p-1)/m+1; bool flag=1;
for(int i=0; i<=mm; ++i) if(s.count(t) && ((ll)m*i-s[t])>=0) { printf("%lld\n", (ll)m*i-s[t]); flag=0; break; } else t=((ll)t*w)%p;
if(flag) puts("no solution");
}
int main() {
int a, b, p;
while(~scanf("%d%d%d", &p, &a, &b)) work(a, b, p);
return 0;
}
bsgs裸题= =
最新文章
- ASP.NET MVC 5 - 创建连接字符串(Connection String)并使用SQL Server LocalDB
- Android图片压缩(质量压缩和尺寸压缩)
- find参数exec、管道符|、xargs的区别
- Selenium获取input输入框中值的三种方法
- linux服务器下tomcat部署项目内存溢出
- Nunit中文文档
- C++实现线程池 .
- MFC基础类源码CPP实现文件
- Vuex初识
- 在DirectShow的视频图像上叠加线条和文字
- TCP 详解
- php定时执行操作及ob_flush()与flush()的使用
- 简单的自定义ViewGroup
- Django提交文件的方式
- Recommender Systems中Yehuda Koren 和 Ma Hao的paper
- Delphi2010中DataSnap技术
- Android API之android.provider.ContactsContract.Contacts
- 手机相册管理(gallery) ---- HTML5+
- Wasserstein GAN
- 不通过注册表使用ActiveX对象