约数之和 (普通快速幂求逆元做法）

约数之和 (普通快速幂求逆元做法）"/>

约数之和 (普通快速幂求逆元做法）

假设现在有两个自然数 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;
}