假設(shè)現(xiàn)在有兩個自然數(shù) A 和 B，S 是 AB

的所有約數(shù)之和。

請你求出 Smod9901

的值是多少。

輸入格式

在一行中輸入用空格隔開的兩個整數(shù) A

和 B

。

輸出格式

輸出一個整數(shù)，代表 Smod9901

的值。

數(shù)據(jù)范圍

0≤A,B≤5×107

輸入樣例：

2 3

輸出樣例：

15

注意: A

和 B 不會同時為 0。

思路

??????? 因為要求p^0+p^1+...+p^k-1，所以這是一個等比數(shù)列，完全可以用快速冪求逆元然后用等比數(shù)列求和公式得到答案

#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"//交互題一定要關(guā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)//獲得質(zhì)因數(shù)
{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函數(shù)
{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的倍數(shù)的話那么其實就是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;
}