One sentence question :G Of sigma d|n  C(n d) The next power   mod 999911659

( I'm so spicy. I still can't mathjax)

analysis :

1. Using Euler's theorem to simplify modular operations , Set the upper power to x, be x= simple form mod 999911658.

2. It is found that the first half of the power is too large to be calculated directly , Again because 999911658 Decomposable into 2 3 4679 35617 Four prime numbers

3. Using Chinese remainder theorem, we can calculate respectively x=a1(mod m1=2) ... Finally, use it to calculate x

4. Fast exponentiation calculates the answer

#define int long long
#define rep(i,x,y) for(register int i=x;i<=y;i++)
#define dec(i,x,y) for(register int i=x;i>=y;i--)
using namespace std; const int mod=; int n,g,m[]={,,,,},a[];
int fac[][]; inline int qpow(int a,int n,int p){
int s=;while(n){if(n&) s=s*a%p;a=a*a%p;n>>=;}return s;} inline void init(){
fac[i][j]=fac[i-][j]*i%m[j];} inline int C(int a,int b,int c){
if(a<b) return ;
return fac[a][c]*qpow(fac[b][c],m[c]-,m[c])%m[c]*qpow(fac[a-b][c],m[c]-,m[c])%m[c]; } inline int Lucas(int a,int b,int c){
if(!b) return ;
return C(a%m[c],b%m[c],c)*Lucas(a/m[c],b/m[c],c)%m[c];} inline void work(int i){
rep(j,,) a[j]=(a[j]+Lucas(n,i,j))%m[j];} inline int CRT(){ int x=,M=mod-;
rep(i,,){ int Mi=M/m[i];
x=(x+a[i]*Mi*qpow(Mi,m[i]-,m[i])%M)%M;}return x;} #undef int
int main(){
#define int long long
scanf("%lld%lld",&n,&g); init();
if(g%mod==) {printf("");return ;} rep(i,,sqrt(n))
if(n%i==){ work(i);
if(i*i!=n) work(n/i);} printf("%lld\n",qpow(g,CRT(),mod));return ;

luogu 2480 Ancient pig writing A collection of number theories (CRT+Lucas+qpow+ Inverse element ) More articles about

  1. BZOJ 1951: [Sdoi2010] Ancient pig writing ( number theory )

    The obvious answer is G^∑C(d,N)(d|N).O(N^0.5) enumeration N The divisor of . Take the number of modules 999911659 Prime number , Consider Euler's theorem a^phi(p)=1(mod p)(a And p Coprime ), that a^t mod p = a ...

  2. 【bzoj1951】: [Sdoi2010] Ancient pig writing number theory - Chinese remainder theorem -Lucas Theorem

    [bzoj1951]: [Sdoi2010] Ancient pig writing because 999911659 It's a prime Euler's theorem leads to And then the Chinese Remainder Theorem on the index And then separately lucas The theorem is good Be careful G==P It's the special judgment of the time /* http://w ...

  3. BZOJ-1951 Ancient pig writing ( Modular of combinatorial data Lucas+ Chinese remainder theorem + Expand Euclid + Fast power )

    It's the number theory 1951: [Sdoi2010] Ancient pig writing Time Limit: 1 Sec Memory Limit: 64 MB Submit: 1573 Solved: 650 [Submit ...

  4. [bzoj1951] [Sdoi2010] Ancient pig writing Fermat's small Theorem +Lucas Theorem +CRT

    Description " On the other side of the mountain, on the other side of the sea, there are a group of little pigs . They are lively and smart , They are naughty and sensitive . They live freely on the big green lawn , They are kind and brave and care for each other --" -- From pig Kingdom folk songs Very long ...

  5. bzoj1951 [Sdoi2010] Ancient pig writing —— Number theory synthesis

    subject : The meaning of the question is to ask for G^( ∑(k|n) C(n,k) ) % p, Deal with exponents with Fermat's theorem , Lou ...

  6. BZOJ.1951.[SDOI2010] Ancient pig writing ( Fermat's small Theorem Lucas CRT)

    Topic link \(Description\) Given N,G, seek \[G^{\sum_{k|N}C_n^k}\mod\ 999911659\] \(Solution\) From Fermat's small theorem , You can simplify the number of times first , The o \( ...

  7. 【bzoj1951】[Sdoi2010] Ancient pig writing Fermat's small Theorem +Lucas Theorem + Chinese remainder theorem

    Title Description seek   $g^{\sum\limits_{k|n}C_{n}^{\frac nk}}\mod 999911659$ Input There is and only one line : Two Numbers N.G, Separate... With a space . Output There is and only one line : One ...

  8. luogu_2480: Ancient pig writing

    Luogu :2480 Ancient pig writing Description of the question : Given two integers \(N,G\), seek $G^{\sum_{k|n}C_n^k} mod 999911659 $. Data range : \(1\leq N\leq 10^9,1\le ...

  9. Ancient pig writing : The big set of number theory : Euler theorem ,exgcd,china, Inverse element ,Lucas Application of Theorem

    /* Ancient pig writing :Lucas Theorem + Chinese remainder theorem 999911658=2*3*4679*35617 Lucas Theorem :(m,n)=(sp,tp)(r,q) %p Chinese remainder theorem :x=sum{si*Mi*ti} ...

Random recommendation

  1. DAC Usage4: from Backup Package(.bacpac) Restore DB

    Use DAC, To be able to database Of schema and data From a server or cloud Copy to another server On , Storage schema and data My file is .bacpac file . Method ...

  2. curl Specific explanation of the order

    by windows Suppose the user Cygwin simulation unix Environment , There won't be a belt curl command , Having the equipment , It is recommended to use Gow To simulate , It already has its own curl Tools , After direct installation cmd Usage environment curl The command can , Because the path is our own master ...

  3. XNA 4.0 Environment building and Hello World,Windows Phone Game development

    XNA 4.0 Environment building and Hello World,Windows Phone Game development Use Scene Class in XNA Create different scenes in ( 8、 ... and ) Abstract : Square has developed some Windows Phone ...

  4. RabbitMq 6 There are two modes of use

    RabbitMQ Of 5 There are two patterns and examples 1.1 Simple mode Hello World function : A producer P Send message to queue Q, A consumer C receive The producer realizes the idea : Create connection factory ConnectionFactory, Setup service ...

  5. js The global variables of and window object

    All variables declared in the global scope . Functions will become window Properties and methods of objects . namely : var age = 55; Can pass window.age visit However, the sum of global variables is related to window There's still a little bit of a gap in the properties defined on the object ...

  6. CentOS7 Set up cluster time synchronization

    1. install ntp Time synchronization tool yum -y install ntp ntpdate # install ntpdate Time synchronization tool ntpdate # Set time synchronization hwclock - ...

  7. php in @mysql_connect And mysql_connect What's the difference?

    Shielding errors, if any , Will show all the statements . Add @ Do not show $link=@mysql_connect('localhost','root','123') or die (" Database connection failed " ...

  8. 20155201 2016-2017-2《Java Programming 》 Course summary

    20155201 2016-2017-2<Java Programming > Course summary Catalog One . Weekly homework link summary Two . Experimental report link summary 3、 ... and . Code managed Links Four . Classroom project practice 5、 ... and . The gains and shortcomings of the course 6、 ... and . The questionnaire survey ...

  9. C Language : Wide character set operation function (unicode code )

    C Language : Wide character set operation function (unicode code ) Character classification : Wide character function Ordinary C Function description iswalnum() isalnum() Test whether characters are numbers or letters iswalpha() isalpha() measuring ...

  10. by openstack Service enables debug Pattern

    Most OpenStack services use the same configuration options to enable the debug logging that is also ...