The Luckiest number HDU - 2462
2021/6/3 10:51:16
本文主要是介绍The Luckiest number HDU - 2462,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
原题链接
考察:欧拉定理
思路:
已知每个8888...888都可以被表示成:
根据欧拉定理,若10与\(\frac{9\times L}{gcd(8,L)}\)互质,则存在最小的正整数x,使得等式成立,而x是\(\frac{9\times L}{gcd(8,L)}\)欧拉函数的约数.
注意那个gcd(9*L,8)也没有关系,9存不存在无所谓,只要与10存在公约数>1即可输出0.
Code
#include <iostream> #include <vector> #include <algorithm> using namespace std; typedef long long LL; LL L; vector<LL> v; LL gcd(LL a,LL b) { return b?gcd(b,a%b):a; } void GetDivide(LL n) { v.clear(); for(int i=1;i<=n/i;i++) { if(n%i==0) { v.push_back(i); if(i!=n/i) v.push_back(n/i); } } sort(v.begin(),v.end()); } LL mul(LL a,LL k,LL m) { LL res = 0; while(k) { if(k&1) res = (res+a)%m; a = (a+a)%m; k>>=1; } return res; } LL qsm(LL a,LL k,LL m) { LL res = 1; while(k) { if(k&1) res = mul(res,a,m); a = mul(a,a,m); k>>=1; } return res; } LL get_er(LL n) { LL res = n; for(LL i=2;i<=n/i;i++) { if(n%i==0) { res = res/i*(i-1); while(n%i==0) n/=i; } } if(n>1) res = res/n*(n-1); return res; } int main() { int kcase = 0; while(scanf("%lld",&L)!=EOF&&L) { LL s = 9*L/gcd(8,L); printf("Case %d: ",++kcase); if(gcd(s,10)>1) {printf("0\n");continue;} GetDivide(get_er(s)); for(int i=0;i<v.size();i++) { LL x = v[i]; if(qsm(10,x,s)==1) {printf("%lld\n",x);break;} } } return 0; }
这篇关于The Luckiest number HDU - 2462的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-05-01巧用 TiCDC Syncpoint 构建银行实时交易和准实时计算一体化架构
- 2024-05-01银行核心背后的落地工程体系丨Oracle - TiDB 数据迁移详解
- 2024-04-26高性能表格工具VTable总体构成-icode9专业技术文章分享
- 2024-04-16软路由代理问题, tg 无法代理问题-icode9专业技术文章分享
- 2024-04-16程序猿用什么锅-icode9专业技术文章分享
- 2024-04-16自建 NAS 的方案-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数-icode9专业技术文章分享
- 2024-04-14ansible 在远程主机上执行脚本,并传入参数, 加上remote_src: yes 配置-icode9专业技术文章分享
- 2024-04-14ansible 检测远程主机的8080端口,如果关闭,则echo 进程已关闭-icode9专业技术文章分享
- 2024-04-14result 成功怎么写-icode9专业技术文章分享