Enter two positive integers \(a\) and \(b\), seek \(a\cdot b\) The factor and . result too large , Just output it to 9901 The remainder of .

Input

Just one line , For two positive integers \(a\) and \(b\)(\(0≤a,b≤50000000\)).

Output

a^b The factor and the pair of 9901 The remainder of .

Sample Input

2 3

Sample Output

15

The question :

Chinese questions , Don't explain .

Answer key :

take \(a^b\) It is divided into \(b\) individual \(a\) Multiply , And then deal with .

set up

\(a=p_1^{c_1}p_2^{c_2}…p_n^{c_n}\)

be \(a\) The sum of all the factors is

\(\sum_{i_1=0}^{c_1}\sum_{i_2=0}^{c_2}…\sum_{i_n=0}^{c_n}p_1^{i_1}p_2^{i_2}…p_n^{i_n}\)

And then we can see that each factor is independent , It can be put forward as

\(\prod_{i=1}^{n}\sum_{j=0}^{c_i}p_i^j\)

Now we can deal with each factor separately

Open \(\sum\) It turns out to be an equal ratio sequence :

\(1+p^1+p^2+p^3+…+p^c\)

Then set up the formula of the equal ratio sequence and it becomes

\(\frac{p^{c-1}-1}{p-1}\)

The final answer is

\(\prod_{i=1}^n\frac{p_i^{c_i-1}-1}{p_i-1}\)

forehead , And ride on \(b\)

\(\prod_{i=1}^n\frac{p_i^{c_ib-1}-1}{p_i-1}\)

The denominator here is multiplied by the inverse , But because sometimes \(p_i-1\) Would be 9901 Multiple , Now just multiply the answer by the number of factors .

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll p=9901;
ll mpow(ll a,ll n){
ll ret=1;
while(n){
if(n&1)ret=ret*a%p;
a=a*a%p;
n/=2;
}
return ret;
}
ll a,b,ans=1;
ll prime[1000000],js[1000000],m;
main(){
cin>>a>>b;
int n=a;
for(ll i=2;i*i<=n;++i){
if(n%i==0)prime[++m]=i;
while(n%i==0){
js[m]++;
n/=i;
}
}
if(n!=1){
prime[++m]=n;
js[m]=1;
}
for(ll i=1;i<=m;++i){
if(prime[i]%p==1){
ans=(ans*(js[i]+1))%p;
continue;
}
ll S=(mpow(prime[i],js[i]*b+1)-1)*mpow(prime[i]-1,p-2)%p;
ans=(ans*S)%p;
}
cout<<ans%p<<endl;
}

Factor and (luoguP1593)( Sum of equal ratio sequence + Inverse element ) More articles about

  1. Codeforces 963A Alternating Sum( Sum of equal ratio sequence + Inverse element + Fast power )

    Topic link :http://codeforces.com/problemset/problem/963/A The main idea of the topic : It's for you n,a,b And a length of k Only '+' and ‘-’ character string , Guarantee n+1 By k to be divisible by , Let you ...

  2. POJ 1845 ( Sum of divisors + Sum of bisection equal ratio sequence )

    Topic link : http://poj.org/problem?id=1845 The main idea of the topic :A^B All divisors of and ,mod 9901. Their thinking : ① The unique decomposition theorem of integers : An integer A It must be divided into :A=(P1^K1) ...

  3. hoj3152-Dice The sum and modulus of equal ratio sequence

    http://acm.hit.edu.cn/hoj/problem/view?id=3152 Dice My Tags (Edit) Source : Time limit : sec Memory ...

  4. luogu1397 [NOI2013] Matrix game ( Sum of equal ratio sequence )

    A more obvious summation of equal ratio sequence , But one problem is n and m huge .. Considering that they appear on the power , So you can mold it P-1( Fermat's small Theorem ) however a or c be equal to 1 When , We can't use the sum formula of the equal ratio sequence , At this time we have to take n and m, It's going to be a mold again P ...

  5. bzoj 4555 [Tjoi2016&amp;Heoi2016] Sum up NTT The second kind of Stirling number Sum optimization of equal ratio sequence

    [Tjoi2016&Heoi2016] Sum up Time Limit: 40 Sec  Memory Limit: 128 MBSubmit: 679  Solved: 534[Submit][S ...

  6. ZOJ-3774 Power of Fibonacci—— Sum of equal ratio sequence &amp;&amp; Equivalent substitution

    subject seek $\displaystyle \sum_{i=1}^n F_i^k$,($1 \leq n\leq 10^{18},1 \leq  k\leq 10^5$), The answer is right $10^9+9$ modulus . ...

  7. 2019 Hebei college students program design competition ( The rematch )B topic -Icebound and Sequence ( Fast power module for summation of equal ratio sequence )

    Topic link :https://ac.nowcoder.com/acm/contest/903/B The question : Here you are. q,n,p, seek q1+q2+...+qn  And model p. Ideas : I couldn't do it at first , After checking, we found that ...

  8. Sumdiv Sum of equal ratio sequence

    Sumdiv Sumdiv Time Limit: 1000MS   Memory Limit: 30000K Total Submissions: 15364   Accepted: 3790 De ...

  9. [zoj 3774]Power of Fibonacci number theory ( Second surplus Expand Euclid Sum of equal ratio sequence )

    Power of Fibonacci Time Limit: 5 Seconds      Memory Limit: 65536 KB In mathematics, Fibonacci numbe ...

Random recommendation

  1. ArcGIS Of Oracle Database requirements

    [ArcGIS There must be a patch ]ArcGIS 10.2.2 for Desktop Connect Oracle(2014 year 10 Published in ) The problem of database crash http://blog.csdn.net/linghe301/art ...

  2. Full exploitation of a cluster hardware configuration requires some enhancements to a single-system operating system.

    COMPUTER ORGANIZATION AND ARCHITECTURE DESIGNING FOR PERFORMANCE NINTH EDITION Operating System Desi ...

  3. Leyi VIP VIP course : Baidu post bar - QQ tribe - QQ Space Post A series of practical video courses

    It's a good tutorial ,3 The actual combat of a set of cases , If you need it, please take a look at the course catalogue of Baidu Post Bar :1. Baidu login packet analysis 2. Baidu login [ Code implementation ]3. Baidu verification code login [ Code implementation ]4. Pay attention to [ Caught analysis ]5. Pay attention to ( Code writing )6. Post Bar Sign in [ ...

  4. Atitit. Trojan virus free killing principle ---sikuli&#160; Use

    Atitit. Trojan virus free killing principle ---sikuli  Use 1.  Use sikuli java api1 1.1. 3. Write code!1 2.  Commonly used api2 2.1. wait  Wait for an interface to show ...

  5. *[topcoder]IncrementingSequence

    http://community.topcoder.com/stat?c=problem_statement&pm=12107 I've been thinking about it for a long time , I caught a glimpse of Greedy, So I think about greed , The last way ...

  6. SQL Server 2008 R2 Versions and components of

    SQL Server 2008 R2 Versions and components of SQL Server 2008 R2   Other versions SQL Server 2008 SQL Server 2005 SQL Server 2012 ...

  7. CentOS(Linux) - SVN Use notes ( Two ) - establish SVN Warehouse and download warehouse to local

    1. install : Reference article CentOS(Linux) - SVN Use notes ( One ) -  install SVN Process and opening and closing svn Service instruction 2. Create repository # Create project directory mkdir /usr/svn# Entry directory cd / ...

  8. The foundation of large numbers 、for And while A simple comparison of cycles

  9. stay CDlinux Download and install the wireless network card driver

    Environmental Science host :ThinkPadT440P System :CDlinux9.7.1 summary Ready to use CDlinux To crack the surrounding wifi Password for free , Because the notebook is new , The system doesn't have its own driver , You can only download it manually on the Internet . Ed ...

  10. [minecraft]mcCoder The feeling of making

    mcCoder It's a minecraft-forge-mod Production Library , Trying to make mod Producers can make it easier mod, Reduce mod The producer's mod It's hard to make . stay GitHub Focus on this project on the Internet : principle mcCoder The main ...