写了几天数论的成果（乐）
错了哥，再也不拿线段树代替树状数组了，TLE了哥
回去学树状数组了(悲)
线段树常数怎么这么大
打开OJ一看诶我怎么树状数组题除了上帝造题七分钟全都做过了
哦原来是线段树过的
-I. Strange Way to Express Integers
EXCRT裸题但是我不会打
看了K8的，看了半天看不懂然后自己打出来了
点击查看代码
#include<bits/stdc++.h>
#define int long long
#define endl "\n"
using namespace std;
const int N=0X66CCFF;
int n,a[N],m[N],b,M;
inline int read(){
int x=0,w= 1;char c=getchar();
while (!isdigit(c)){if(c=='-')w=-1;c=getchar();}
while (isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*w;
}
inline int Exgcd(int a,int b,int&x,int&y) {
if(!b){x=1,y=0;return a;}
int g=Exgcd(b,a%b,x,y),_x=x;
x=y,y=_x-(a/b)*y;
return g;
}
inline int LCM(int a,int b) {
return(a*b/__gcd(a,b));
}
inline int Mul(int a,int b,int MOD) {
int ans=0;
while(b){
if(b&1)ans=(ans+a)%MOD;
a=(a+a)%MOD,b>>=1;
}
return(ans+MOD)%MOD;
}
signed main(){
while(cin>>n){
for(int i=1;i<=n;i++) m[i]=read(),a[i]=read();
b=a[1],M=m[1];
bool f=0;
for(int i=2;i<=n;i++){
int x,y,num=(a[i]-b%m[i]+m[i])%m[i];
int g=Exgcd(M,m[i],x,y);
if(num%g){
f=1;
break;
}
b+=M*Mul(x,num/g,m[i]/g);
M*=m[i]/g,b=(b%M+M)%M;
}
if(f) cout<<-1<<endl;
else cout<<(b%M+M)%M<<endl;
}
}
- 古代猪文
原题来自：SDOI 2010
猪王国的文明源远流长，博大精深。
iPig 在大肥猪学校图书馆中查阅资料，得知远古时期猪文文字总个数为\(N\)
。当然，一种语言如果字数很多，字典也相应会很大。当时的猪王国国王考虑到如果修一本字典，规模有可能远远超过康熙字典，花费的猪力、物力将难以估量。故考虑再三没有进行这一项劳猪伤财之举。当然，猪王国的文字后来随着历史变迁逐渐进行了简化，去掉了一些不常用的字。iPig 打算研究古时某个朝代的猪文文字。根据相关文献记载，那个朝代流传的猪文文字恰好为远古时期的\(k\)分之一，其中\(k\)是\(N\)的一个正约数（可以是\(1\)和\(N\)）。不过具体是哪\(k\)分之一，以及\(k\)是多少，由于历史过于久远，已经无从考证了。
iPig 觉得只要符合文献，每一种能整除 \(N\) 的 \(k\) 都是有可能的。他打算考虑到所有可能的 \(k\) 。显然当 \(k\) 等于某个定值时，该朝的猪文文字个数为 \(\frac k N\)。然而从 \(N\) 个文字中保留下 \(\frac k N\) 个的情况也是相当多的。iPig 预计，如果所有可能的 的所有情况数加起来为\(P\) 的话，那么他研究古代文字的代价将会是 \(G\) 的 \(P\) 次方。
现在他想知道猪王国研究古代文字的代价是多少。由于 iPig 觉得这个数字可能是天文数字，所以你只需要告诉他答案除以 \(999911659\) 的余数就可以了。
什么基础数论全家桶
首先简化题面
- 给定整数\(q\),\(n\)计算
\(q^{\sum_{d|n}^{n}\binom{d}{n}}\bmod 999911659\)
根据费马小定理
又根据唯一分解定理可得
枚举\(d|n\)，用卢卡斯定理求出\(\binom{d}{n}\)(记得预处理对于质数\(2, 3, 4679,35617\)以内的阶乘和阶乘对于\(\bmod\)这些数的逆元)
此时形成了一个同余方程组
用中国剩余定理求解就可以得到\({\large \sum_{d|n}^{n}\binom{d}{n}} \normalsize \bmod 999911658\)的最小正整数解
接着直接快速幂求解\(q^{{\large \sum_{d|n}^{n}\binom{d}{n}} \normalsize \bmod 999911658}\)即可
点击查看代码
#include<bits/stdc++.h>
#define int long long
inline int read(){
int s = 0,w = 1;char ch = getchar();
while(ch<'0'||ch>'9'){ if(ch == '-') w = -1;ch = getchar();}
while(ch>='0'&&ch<='9'){ s = s*10+ch-'0';ch = getchar();}
return s*w;
}
const int maxm=0X66CCFF;
using namespace std;
const int mod=999911659;
const int MOD=999911658;
int n,q;
int prime[4]={2,3,4679,35617};
int ans[maxm],fact[maxm],inv[maxm];
inline int mul(int a,int b,int p){
int r=0;
for(;b;b>>=1,a=(a+a)%p)
if(b&1)
r=(r+a)%p;
return r;
}
inline int qpow(int a,int k,int p){
int res=1;
while(k){
if(k&1) res=res*a%p;
k>>=1;
a=a*a%p;
}
return res;
}
inline int Comb(int n,int m,int p){
return n<m?0:fact[n]*inv[n-m]%p*inv[m]%p;
}
inline int lucas(int a,int b,int p){
if(!a||!b) return 1;
if(a<p&&b<p) return Comb(a,b,p);
return Comb(a%p,b%p,p)*lucas(a/p,b/p,p)%p;
}
inline int CRT(){
int r=0;
for (int i=0;i<4;i++){
int tmp=MOD/prime[i];
r=(r+ans[i]*tmp%MOD*qpow(tmp,prime[i]-2,prime[i])%MOD)%MOD;
}
return r;
}
signed main(){
n=read(),q=read();
if(q==mod){
puts("0");
return 0;
}
for(int i=0;i<4;i++){
fact[0]=fact[1]=inv[0]=1;
for(int j=1;j<=prime[i];j++)
fact[j]=fact[j-1]*j%prime[i];
inv[prime[i]-1]=qpow(fact[prime[i]-1],prime[i]-2,prime[i]);
for(int j=prime[i]-2;j>=1;j--)
inv[j]=inv[j+1]*(j+1)%prime[i];
for(int k=1;k*k<=n;k++)
if(n%k==0){
ans[i]=(ans[i]+lucas(n,k,prime[i]))%prime[i];
if (k*k!=n) ans[i]=(ans[i]+lucas(n,n/k,prime[i]))%prime[i];
}
}
printf("%lld",qpow(q,CRT(),mod)%mod);
}