【约数】因子和
因子 约数
2023-09-11 14:14:52 时间
P1593 因子和 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
题意:
思路:
我们去枚举约数
如果直接枚举约数,超时
对于枚举约数,有两个trick:枚举倍数和唯一分解定理
我们考虑后者,对其分解质因数:
因为它又有b的幂次:
因此答案就是:
这里可以直接用等比数列求和公式:
因为是模意义下的答案,因此考虑逆元
但是mod=9901,容易出现逆元不存在的情况
逆元不存在时,有
即
因此直接代入得
Code:
#include <bits/stdc++.h>
using namespace std;
#define int long long
const int mod=9901;
vector<pair<int,int> > v;
int a,b,ans=1;
int ksm(int a,int b,int mod){
int res=1;
while(b>0){
if(b&1) res=(res*a)%mod;
a=(a*a)%mod;
b>>=1;
}
return res%mod;
}
int calc(int p,int aa){
if((1-p)%mod==0){
return (1+aa)%mod;
}
int inv=ksm(1-p,mod-2,mod);
return ((1-ksm(p,aa*b+1,mod))*inv)%mod;
}
signed main(){
ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
cin>>a>>b;
if(a==0){
cout<<0<<'\n';
return 0;
}
for(int i=2;i<=a/i;i++){
if(a%i==0){
int s=0;
while(a%i==0) a/=i,s++;
v.push_back({i,s});
}
}
if(a>1) v.push_back({a,1});
//for(int i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<'\n';
int ans=1;
for(int i=0;i<v.size();i++){
ans*=calc(v[i].first,v[i].second);
ans%=mod;
}
cout<<(ans%mod+mod)%mod<<'\n';
}
总结:
快速枚举约数:枚举倍数/唯一分解
数太大时考虑唯一分解
当模数比较小时要考虑逆元不存在的情况,不存在的话根据它的性质直接代入计算即可
相关文章
- 【等保】等保测评中双因素认证是什么意思?等于双因子认证吗?
- 多因子认证是什么意思?与双因子认证有什么区别?
- C#,因数分解(质因子分解)Pollard‘s Rho算法的源代码
- 起源自天文学的PostgreSQL 优化器成本因子校对
- HashMap 默认加载因子非得是0.75
- 面试题:HashMap的加载因子
- 输入一个正整数,按照从小到大的顺序输出它的所有质因子(如180的质因子为2 2 3 3 5 )
- 【USACO 3.1】Humble Numbers(给定质因子组成的第n大的数)
- 关于武忠祥老师“可爱因子”的提出结论的原理推导
- R语言入门:因子的使用
- [LeetCode] 1071. Greatest Common Divisor of Strings 字符串的最大公因子
- [CareerCup] 7.7 The Number with Only Prime Factors 只有质数因子的数字
- 电话验证靠谱? 双因子认证或助黑客致富