分类目录归档:数论

Openjudge BJUTACM 181A:素数和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
#include<algorithm>
#include<cstring>
#include<stack>
#include<vector>
#include<typeinfo>
using namespace std;
int n, m;
bool isprime[10000005];
int prime[10000005];
vector<int> 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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include<iostream>
#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

不是特别会做,看了题解,好像还挺简单了,写代码写了挺长时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
#define pii pair<int,int>
#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;
}

数论代码总结

欧几里得:求a,b的最大公约数。

1
2
3
4
int gcd(int a,int b){
    if(b==0)return a;
    return gcd(b,a%b);
}

扩展欧几里得:(求a,b的最大公约数和不定方程ax+by=d(=gcd(a,b))的一对解)
裴蜀定理
对于任意整数 $a$ , $b$,存在无穷多组整数对 $(x,y)$ 满足不定方程 $ax+by=d$ ,其中 $d=gcd(a,b)$。
在求 $d=gcd(a,b)$的同时,可以求出关于x,y的不定方程$ax+by=d$的一组整数解。
考虑递归计算:假设已经算出了$(b,a \bmod b)$的一对解$(x_0,y_0)$满足$bx_0+(a \bmod b)y_0=d$。
可以得到$bx_0+(a – b \left \lfloor \frac{a}{b} \right \rfloor)y_0=d$。
整理可得$b(x_0-\left \lfloor \frac{a}{b} \right \rfloor y_0) +ay_0=d$。
即$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$。
假设先行$swap(x_0,y_0)$,则有$x=x_0,y=y_0-\left \lfloor \frac{a}{b} \right \rfloor x_0$。

1
2
3
4
5
6
7
8
9
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;
}

乘法逆元
方法1:利用扩展欧几里得求逆元,参见:https://renjikai.com/luogu-p1082/
适用条件:被求数a和模数b互质。
方法2:利用费马小定理(快速幂)求逆元,参见:https://renjikai.com/luogu-p1313/
适用条件:模数为质数。(保证了被求数a和模数b互质。)
方法3:不用记复杂的线性递推公式,就可以用O(N)复杂度推出1到n的所有乘法逆元(模意义下,在后面不再赘述)。除此之外,在此过程中求出$1!$到$n!$的阶乘及其逆元。
前提结论:易知$\prod_{i=1}^{n}\ inv(i)=inv(n!)$。
乘法逆元定义:$inv(i)\cdot i\equiv 1$
令数组$A_i=i!$,容易求出数组A。令数组$B_i=inv(i!)$,那么数组B应该怎么求呢?
用方法1、2容易求出$inv(A_n)$,即$inv(n!)$,即求出了$B_n$。
由前提结论知,$B$数组的递推公式为$B_i=B_{i-1} \cdot inv(i)$,两边同乘$i$,则有$B_i \cdot i =B_{i-1} \cdot inv(i)\cdot i$,由乘法逆元定义有$B_{i-1} = B_i \cdot i $,只需回推,即可求出由$i!$的乘法逆元。
因$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++伪代码如下:(不一定完全正确,请注意识别)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#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;
    }
}

洛谷 同余方程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include<bits/stdc++.h>
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/

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#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;
}

洛谷 计算系数

题号:P1313
大晚上的刷杨辉三角………………

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
#include<iostream>
#include<cstdio>
#include<string>
#include<algorithm>
#include<queue>
#include<map>
#include<list>
#include<cstring>
#include<cassert>
#include<cmath>
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更新:
不用杨辉三角啦!因为我会乘法逆元啦!!!哈哈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<cstring>
#define ll long long
#define pii pair<int,int>
#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

题目编号:1865
用到的思想,一维前缀和,埃式素数筛

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#include<string>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<iostream>
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"<<endl;
            continue;
        }
        cout<<prefixsum[r]-prefixsum[l-1]<<endl;
    }
}