本文主要是介绍约数之和 (普通快速幂求逆元做法），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
假设现在有两个自然数 A 和 B，S 是 AB
的所有约数之和。
请你求出 Smod9901
的值是多少。
输入格式
在一行中输入用空格隔开的两个整数 A
和 B
。
输出格式
输出一个整数，代表 Smod9901
的值。
数据范围
0≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A
和 B 不会同时为 0。
思路
因为要求p^0+p^1+...+p^k-1，所以这是一个等比数列，完全可以用快速幂求逆元然后用等比数列求和公式得到答案
#include<iostream>
#include<cmath>
#include<cstring>
#include<cstdio>
#include<stack>
#include<string>
#include<algorithm>
#include<unordered_map>
#include<map>
#include<bitset>
#include<cstring>
#include <unordered_set>
//#include<priority_queue>
#include<queue>
#include<deque>
#include<set>
#include<stdlib.h>
#define dbug cout<<"*****hear*****"<<endl;
#define rep(a,b,c) for(ll a=b;a<=c;a++)
#define per(a,b,c) for(ll a=b;a>=c;a--)
#define no cout<<"NO"<<endl;
#define yes cout<<"YES"<<endl;
#define endl "\n"//交互题一定要关！！！！！！！！！
#define lowbit(x) (x&-x)
#define IOS ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
//priority_queue<int,vector<int>,greater<int> >q;
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> PII;
typedef pair<long double,long double> PDD;ll INF = 0x3f3f3f3f;
//const ll LINF=LLONG_MAX;
// int get_len(int x1,int y1,int x2,int y2)
// {
// return (x2-x1)*(x2-x1) + (y2-y1)*(y2-y1);
// }
const ll N = 2e5+ 10;const ll mod1 =998244353;const ll mod2 =1e9+7;
// const ll hash_num = 3e9+9;
ll n,m,ca;
ll arr[N],brr[N],crr[N],drr[N];
//ll h[N],ne[N],e[N],w[N],book[N],idx;
//ll idx;// void add(ll a, ll b , ll c)
// {
// e[idx] = b, w[idx] = c,ne[idx] = h[a], h[a] =idx ++ ;
// }
ll mod=9901;
unordered_map<ll,ll>prime;ll fast_power(ll a,ll b)//快速幂
{ll res=1;while(b){if(b&1)res=res*a%mod;b >>= 1;a=a*a%mod;}return res;
}void get(ll x)//获得质因数
{for(ll i=2;i<=x/i;i++){while(x%i==0){x/=i;prime[i]++;}}if(x>1)prime[x]++;
}ll sum(ll p,ll k)//sum函数
{if(k==1)return 1;if(k%2==0){return (1+fast_power(p,k/2))*sum(p,k/2)%mod;}else{return (fast_power(p, k - 1) + sum(p, k - 1)) % mod;}
}void solve()
{cin >> n >> m;get(n);ll ans=1;for(auto it : prime){ll a = it.first, b = it.second * m;if((a-1)%mod==0)//如果a-1是mod的倍数的话那么其实就是k+1个1相加{ans=ans*(b+1)%mod;}else{ans=ans*(fast_power(a,b+1)-1)%mod*(fast_power(a-1,mod-2))%mod;//这里是将求和公式上下都提取一个负号变成了(a^b+1)-1和a-1}}if(!n)ans=0;cout << (ans%mod+mod)%mod;
}int main()
{IOS;ll _;_=1;//scanf("%lld",&_);// cin>>_;ca=1;while(_--){solve(); ca++;} return 0;
}
这篇关于约数之和 (普通快速幂求逆元做法）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
