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

#include<bits/stdc++.h>

#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[][]=fac[][]=fac[][]=fac[][]=;

rep(i,,)rep(j,,)

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

- 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 ...

- 【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 ...

- 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 ...

- [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 ...

- bzoj1951 [Sdoi2010] Ancient pig writing —— Number theory synthesis
subject :https://www.lydsy.com/JudgeOnline/problem.php?id=1951 The meaning of the question is to ask for G^( ∑(k|n) C(n,k) ) % p, Deal with exponents with Fermat's theorem , Lou ...

- 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 \( ...

- 【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 ...

- 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 ...

- 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

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- 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 ...

- CentOS7 Set up cluster time synchronization
1. install ntp Time synchronization tool yum -y install ntp ntpdate # install ntpdate Time synchronization tool ntpdate cn.pool.ntp.org # Set time synchronization hwclock - ...

- 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 " ...

- 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 ...

- 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 ...

- by openstack Service enables debug Pattern
Most OpenStack services use the same configuration options to enable the debug logging that is also ...