# 洛谷 P4777 【模板】扩展中国剩余定理（EXCRT）

https://www.luogu.org/blog/niiick/solution-p4777
https://www.luogu.org/problemnew/solution/P4777
https://blog.csdn.net/xiaobian_/article/details/87949337

https://www.cnblogs.com/yangsongyi/p/9867057.html
（快速乘规避溢出）
https://www.cnblogs.com/jt2001/p/6129914.html
https://blog.csdn.net/qq_39599067/article/details/81118467

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546 #include #include #include #include using namespace std; typedef long long ll; int n; ll b[100005], a[100005]; //b是余数，a是模数 ll quickmultiply(ll a, ll b,ll mod) {     if (b == 0)return 0;     ll result = quickmultiply(a, b / 2, mod) % mod;     result = 2*result%mod;     if (b & 1)result = (result+a)%mod;     return result; } ll ngcd(ll a, ll b) {     return b == 0 ? a : ngcd(b, a % b); } ll exgcd(ll a, ll b, ll& x, ll& y) {     if (b == 0) {         x = 1; y = 0;         return a;     }     ll d = exgcd(b, a % b, y, x);     y -= a / b * x;     return d; } ll excrt() {     ll lcm = a[1], ans = b[1];     for (int i = 2; i <= n; i++) {         ll k1, k2, K, mod = lcm;         ll gcd = exgcd(lcm, a[i], k1, k2);         ll minus = ((b[i] - ans) % a[i] + a[i]) % a[i];         if ((minus % ngcd(lcm, a[i]) != 0))return -1;         K = (quickmultiply(k1,(minus / gcd),(a[i] / gcd)) + a[i] / gcd) % (a[i] / gcd);         lcm *= a[i] / gcd, ans = (K * mod + ans) % lcm;     }     return (ans % lcm + lcm) % lcm; } int main() {     cin >> n;     for (int i = 1; i <= n; i++) {         cin >> a[i] >> b[i];     }     cout<

# 计蒜客 Random Access Iterator

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #define MOD 1000000007 #define ll long long using namespace std; int n; int MDep; vector edges[1000005]; bool visited[1000005]; ll quickpow(ll a, ll b) {     if (b == 0)return 1;     ll re = quickpow(a, b / 2) % MOD;     re = (re * re) % MOD;     if (b % 2 == 1)re *= a % MOD;     return re % MOD; } inline ll inv(ll x) {     return quickpow(x, MOD - 2) % MOD; } inline ll chance1(ll TotNode) {     ll ch = (inv(TotNode)) % MOD;     return ch; } inline ll chance2(ll onceCh,ll TotNode) {     ll onceNonch = (1ll-onceCh+MOD) % MOD;     ll nonch = quickpow(onceNonch, TotNode);     ll fin = (1ll - nonch + MOD) % MOD;     return fin; } int dfsMaxDep(int node) {     int maxDep = 1;     bool hasChild = false;     visited[node] = true;     for (int i = 0; i < edges[node].size(); i++) {         if (visited[edges[node][i]])continue;         hasChild = true;         maxDep = max(maxDep, dfsMaxDep(edges[node][i]) + 1);     }     return maxDep; } ll dfsChance(int depth,int node){     if (depth == MDep)return 1;     ll ch = 0,sCh=chance1(node==1?edges[node].size(): edges[node].size()-1);     visited[node] = true;     for (int i = 0; i < edges[node].size(); i++) {         if (visited[edges[node][i]])continue;         ll CurCH = dfsChance(depth + 1, edges[node][i]);         if (CurCH) {             ch += (CurCH * sCh) % MOD;             ch %= MOD;         }     }     return chance2(ch, node == 1 ? edges[node].size() : edges[node].size() - 1); } int main() {     ios::sync_with_stdio(false);     cin.tie(0);     cin >> n;     for (int i = 1; i < n; i++) {         int u, v;         cin >> u >> v;         edges[u].push_back(v);         edges[v].push_back(u);     }     MDep = dfsMaxDep(1);     memset(visited, false, sizeof(visited));     ll ch = dfsChance(1, 1);     cout << ch; }

# Openjudge BJUTACM 181A:素数和

 12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455 #define _CRT_SECURE_NO_WARNINGS #include #include #include #include #include #include using namespace std; int n, m; bool isprime[10000005]; int prime[10000005]; vector primeList; inline void genPrime() {     memset(isprime, true, sizeof(isprime));     isprime[0] = isprime[1] = false;     for (int i = 2; i <= 10000000; i++) {         if (!isprime[i])continue;         primeList.push_back(i);         for (int j = 2 * i; j <= 10000000; j += i) {             isprime[j] = false;         }     } } inline void putIn(int v) {     for (int i = 0; i < primeList.size() && v >= primeList[i] && v != 1; i++) {         if (v%primeList[i] == 0) {             prime[primeList[i]]++;             while (v%primeList[i] == 0)v /= primeList[i];         }         if (isprime[v]) {             prime[v]++;             break;         }     } } int main() {     genPrime();     scanf("%d", &n);     for (int i = 1; i <= n; i++) {         int v;         scanf("%d", &v);         putIn(v);     }     for (int i = 1; i <= 10000000; i++) {         prime[i] += prime[i - 1];     }     scanf("%d", &m);     for (int i = 1; i <= m; i++) {         int l, r;         scanf("%d%d", &l, &r);         if (r > 10000000)r = 10000000;         if (l > 10000000)l = 10000000;         printf("%d\n", prime[r] - prime[l - 1]);     } }

http://bjutacm.openjudge.cn/lianxi/181A/

# 洛谷 P1641 [SCOI2010]生成字符串

https://www.luogu.org/blog/user29936/solution-p1641
https://www.luogu.org/blog/user35379/solution-p1641

 12345678910111213141516171819202122232425262728293031 #include #define ll long long #define MOD 20100403 using namespace std; ll quickpow(ll a,ll b){     if(b==0)return 1;     ll re=quickpow(a,b/2)%MOD;     re=re*re%MOD;     if(b%2!=0)re=re*a%MOD;     return re%MOD; } ll inv(ll x){     return quickpow(x,MOD-2)%MOD; } ll C(ll n,ll m){     ll re=1;     for(ll i=n;i>=n-m+1;i--){         re=re*i%MOD;     }     ll fact=1;     for(ll i=1;i<=m;i++){         fact=fact*i%MOD;     }     ll invFact=inv(fact);     return re*invFact%MOD; } int main(){     ll n,m;     cin>>n>>m;     cout<<(C(n+m,n)%MOD-C(n+m,n+1)%MOD+MOD)%MOD; }

# 洛谷 P1414 又是毕业季II

 12345678910111213141516171819202122232425262728293031323334 #include #include #include #define ll long long #define pii pair #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; int n; int score[10005]; int cnts[1000005]; int cnts2[10005]; int main() {     ios::sync_with_stdio(false);     cin >> n;     cnts[1] = n;     for (int i = 1; i <= n; i++)cin >> score[i];     int maxV = 0;     for (int i = 1; i <= n; i++) {         if (score[i] != 1)cnts[score[i]]++;         maxV = max(maxV, score[i]);         for (int j = 2; j <= sqrt((double)score[i]); j++) {             if (score[i] % j == 0) {                 cnts[j]++;                 if (j*j != score[i])cnts[score[i] / j]++;             }         }     }     for (int i = 1; i <= maxV; i++) {         if(cnts[i]!=0)cnts2[cnts[i]] = i;     }     for (int i = n; i > 0; i--)cnts2[i] = max(cnts2[i], cnts2[i + 1]);     for (int i = 1; i <= n; i++)cout << cnts2[i] << endl; }

# 数论代码总结

int gcd(int a,int b){
if(b==0)return a;
return gcd(b,a%b);
}

ay_0+b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0)=d
x=y_0,y=x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0

int exgcd(int a,int b,int &x,int &y){
if(b==0){
x=1;y=0;
return a;
}
int d=exgcd(b,a%b,y,x);
y-=a/b*x;
return d;
}

B_n=\prod_{i=1}^{n} inv(i)=inv(n)\cdot inv(n-1) \cdot inv(n-2) … \cdot inv(1)A_{n-1}=(n-1)!=(n-1)\cdot(n-2)…\cdot(1)，因此两式相乘则有inv(n)=B_{n\cdot A}{n-1}，即求出了1到n的所有乘法逆元，是线性复杂度O(N)，可能常数大一点，但是好记啊。
C++伪代码如下：（不一定完全正确，请注意识别）

#define MOD
#define ll long long

ll quickpow(ll a, ll b);
ll fInv(ll x) {
return quickpow(x, MOD - 2) % MOD;
}
ll n;
ll fact[n + 2];
ll invFact[n + 2];
ll inv[n + 2];
void gen() {
fact[1] = 1;
for (ll i = 2; i <= n; i++) {
fact[i] = (fact[i - 1] * i) % MOD;
}
invFact[n] = fInv(fact[n]);
for (ll i = n - 1; i >= 1; i--) {
invFact[i] = invFact[i + 1] * (i + 1) % MOD;
}
inv[1] = 1;
for (ll i = 2; i <= n; i++) {
inv[i] = invFact[i] * fact[i - 1] % MOD;
}
}


# 洛谷 同余方程

 12345678910111213141516171819202122 #include using namespace std; long long exgcd(long long a, long long b, long long &x1, long long &y1){     if (b == 0){         x1 = 1; y1 = 0;         return a;     }     long long x, y;     long long r = exgcd(b, a%b, x, y);     x1 = y;     y1 = x - a / b*y;     return r; } int main(){     ios::sync_with_stdio(false);     long long a, b;     cin >> a >> b;     long long x, y;     exgcd(a, b, x, y);     cout << (x + b) % b; }

20180807更新：
exgcd证明过程参见：https://renjikai.com/cpp-number-theory/

 12345678910111213141516171819202122232425 #include #include #include #include #include #define ll long long #define pii pair #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; ll exgcd(ll a, ll b, ll &x, ll &y) {     if (b == 0) {         x = 1; y = 0;         return a;     }     ll d = exgcd(b, a%b, y, x);     y -= a / b * x;     return d; } int main() {     ll a, b, x, y;     cin >> a >> b;     exgcd(a, b, x, y);     cout << (x%b + b) % b; }

# 洛谷 计算系数

 123456789101112131415161718192021222324252627282930313233343536373839404142 #include #include #include #include #include #include #include #include #include #include using namespace std; #define MOD 10007 long long arr[1005][1005]; long long a, b, k, n, m; long long quickpow(long long x, long long y){     if (y == 0)return 1;     long long qpsqr2 = quickpow(x, y / 2)%MOD;     if (y % 2 == 0){         return (qpsqr2*qpsqr2) % MOD;     }     else{         return (((qpsqr2*qpsqr2) % MOD)*(x%MOD)) % MOD;     } } int main(){     ios::sync_with_stdio(false);     cin >> a >> b >> k >> n >> m;     for (int i = 0; i <= 1000; i++){         arr[0][i] = 1;         arr[i][i] = 1;     }     for (int i = 1; i <= 1000; i++){         for (int j = 1; j < i; j++){             arr[j][i] = (arr[j][i - 1] % MOD + arr[j - 1][i - 1] % MOD) % MOD;         }     }     long long ans = arr[n][k];     ans = (ans*quickpow(a, n)) % MOD;     ans = (ans*quickpow(b, m)) % MOD;     cout << ans;     return 0; }

20180808更新：

 123456789101112131415161718192021222324252627282930313233343536373839 #include #include #include #include #include #define ll long long #define pii pair #define PINF 0x7fffffff #define NINF 0x80000000 using namespace std; #define MOD 10007 ll a,b,k,n,m; //C(min(n,m),k)*b^m*a^n ll quickpow(ll a, ll b) {     if (b == 0)return 1;     ll re = quickpow(a, b / 2) % MOD;     re = (re*re) % MOD;     if (b % 2 == 1)re *= a % MOD;     return re % MOD; } ll inv(ll x) {     return quickpow(x, MOD - 2) % MOD; } int main() {     cin >> a >> b >> k >> n >> m;     ll re = (quickpow(a, n)*quickpow(b, m)) % MOD;     ll cU = 1;     for (ll i = k; i >= k - min(n, m) + 1; i--) {         cU *= i % MOD;         cU %= MOD;     }     ll cD = 1;     for (ll i = 1; i <= min(n, m); i++) {         cD *= i % MOD;         cD %= MOD;     }     re = ((re * cU) % MOD*inv(cD)) % MOD;     cout << re; }

# 洛谷 A % B Problem

 123456789101112131415161718192021222324252627282930313233 #include #include #include #include #include using namespace std; bool prime[1000005]; int prefixsum[1000005]; int main(){     ios::sync_with_stdio(false);     int n,m;     cin>>n>>m;     memset(prime,true,sizeof(prime));     prime[1]=false;     for(int i=2;i<=m;i++){         if(!prime[i])continue;         for(int j=2;i*j<=m;j++){             prime[i*j]=false;         }     }     for(int i=1;i<=m;i++){         prefixsum[i]=prefixsum[i-1]+prime[i];     }     for(int i=1;i<=n;i++){         int l,r;         cin>>l>>r;         if(l<1||r>m){             cout<<"Crossing the line"<