Acdreamer博客数论学习(2)

acm

Acdreamer 博客学习(2)

Day Three

组合数取模/Lucas

  1. $1 \le m \le n \le 1000,1 \le p \le 10^9$,杨辉三角算一下
  2. $1 \le m \le n \le 10^{18}, 2 \le p \le 10^5$,p为素数,卢卡斯定理$n=n_kp^{k}+n_{k-1}p^{k-1}+…+n_1p+n_0$，$m=m_kp^k+m_{k-1}p^{k-1}+…+m_1p+m_0$

有$C_n^m = \prod_{i=0}C_{n_i}^{m_i} (mod \ p) $

这样分别求，采用逆元计算，逆元时乘以了$b^{m-1}\equiv 1(mod \ m)$

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<cstdio>
#include<iostream>
#define ll long long
using namespace std;

ll n,m,p;

ll quick_mod(ll a, ll b){
    ll ans = 1;
    a %= p;
    while(b){
        if(b&1)ans = ans*a%p;
        a = a*a%p;
        b>>=1;
    }
    return ans;
}
//逆元p \equiv
ll C(ll n, ll m){
    if(m > n)return 0;
    ll ans = 1;
    for(int i = 1; i <= m; i++){
        ll a = (n+i-m)%p;
        ll b = i%p;
        ans = ans * (a*quick_mod(b, p-2)%p)%p;
    }
    return ans;
}

ll Lucas(ll n, ll m){
    if(m==0)return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p);
}

int main(){
    int T;scanf("%d",&T);
    while(T--){
        scanf("%lld%lld%lld",&n,&m,&p);
        printf("%lld\n",Lucas(n,m));
    }
    return 0;
}
  1. $ 1 \le m \le n \le 10^6$和$1 \le p \le 10^5$,并且p可能合数．

先采取暴力分解，然后快速幂．

题意:给你一个长为m，宽为n的矩形，求从左上角到右下角经过最少步数的走法有多少种,就是我们常说的非降路径数。从（a,b）到（m,n)共有C（m+n-a-b,m-a）种.

C（n,m）= n!/(m!*(n-m)!) 将分子和分母分别转化为素因子乘积的形式，然后上下同时约去，最后用快速幂搞一下就行了

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
#include<cstdio>
#include<istream>
#include<cstring>
#include<iostream>
#include<cmath>
#define ll long long
const int maxn = 2e6;
using namespace std;

bool judge[maxn];
int prime[maxn]={0};
int tot=0;


//欧拉筛
void init(){
    memset(judge, 0 ,sizeof judge);
    for(int i = 2; i < maxn; i++){
        if(!judge[i])prime[tot++]=i;
        for(int j = 0; j < tot && i*prime[j]<maxn; j++){
            if(i*prime[j]>maxn)break;
            judge[i*prime[j]]=1;
        }
    }
}
ll quick_mod(ll a, ll b, ll m){
    ll ans = 1;
    a %= m;
    while(b){
        if(b&1)ans = ans*a%m;
        a = a*a%m;
        b>>=1;
    }
    return ans;
}

ll work(ll n, ll p){
    ll ans =0;
    while(n){
        ans += n/p;
        n/=p;
    }
    return ans;
}

ll slove(ll n ,ll m ,ll mod){
    ll ans = 1;
    for(int i = 0; i < tot && prime[i] <= n; i++){
        ll x = work(n,prime[i]);
        ll y = work(n-m,prime[i]);
        ll z = work(m,prime[i]);
        x -= (y+z);
        ans *= quick_mod(prime[i],x,mod);
        ans %= mod;
    }
    return ans;
}


int main(){
    int T,t=0;scanf("%d",&T);
    init();
    ll n,m,p;
    while(t++<T){
        scanf("%lld%lld%lld",&n,&m,&p);
        n += m-2;
        m--;
        printf("%lld\n",slove(n,m,p));
    }
    return 0;
}

Lucas习题:

DP?HDU - 3944

处理问题得到一个数学问题$$C_{n+1}^{k+1} +k $$ %p,每次最大处理数据10w,必须做预处理.k<=n<=1e9;

因为给定的p为质数.p<1e4,对于每个素数都每个阶乘都做预处理,计算组合数就可以直接用

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
#include<cstdio>
#include<iostream>
#include<bitset>
const int maxn = 1e4+100;
using namespace std;

int n,k,p;
bitset<maxn> judge;
int prime[maxn];
int ord[maxn];
int fac[maxn][maxn];
int inv[maxn][maxn];
int tot=0;

int power(int a, int b, int mod){
    int ans = 1;
    a%=mod;
    while(b){
        if(b&1)ans = a*ans%mod;
        a = a*a%mod;
        b >>= 1;
    }
    return ans;
}

void init(){
    judge.reset();
    for(int i = 2; i < maxn; i++){
        if(!judge[i]){
            ord[i]=tot;
            prime[tot++]=i;
        }
        for(int j = 0; j < tot ; j++){
            if(i*prime[j]>=maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j]==0)break;
        }
    }

    for(int i = 0; i < tot; i++){
        fac[i][0] = 1;
        inv[i][0] = 1;
        for(int j = 1; j < prime[i]; j++){
            fac[i][j] = (fac[i][j-1]*j)%prime[i];
            inv[i][j] = power(fac[i][j], prime[i]-2, prime[i]);
        }
    }
}

int C(int n, int m){
    if(m>n)return 0;
    if(m==n)return 1;
    int t = ord[p];
    return fac[t][n]*(inv[t][n-m] * inv[t][m]%p)%p;
}

int Lucas(int n, int m){
    if(m==0)return 1;
    return C(n%p,m%p)*Lucas(n/p,m/p)%p;
}

void test(){
    return ;
}

int main(){
    int t = 0;init();
    test();
    while(~scanf("%d%d%d",&n,&k,&p)){
        if(k<=(n/2))k = n-k;
        printf("Case #%d: %d\n",++t,((k+Lucas(n+1,k+1))%p)%p);
    }
    return 0;
}

Xiao Ming’s Hope HDU - 4349

求$$C_n^0, C_n^1,…C_n^n$$中奇数的个数.将n转化为二进制,二进制中1的个数为n,答案就是2^n;

CRT(中国剩余定理)

$$
m_1,m_2,…,m_k两两互素,则同余方程组x \equiv a_1 (mod \ m_1)\ x\equiv a_2 (mod \ m_2) \ … \ x\equiv a_k (mod \ m_k)
\ 模M = m_1 m_2m_3 …m_k 解为x \equiv (a_1M_1M_1^{-1} + a_2M_2M_2^{-1} +…+a_kM_kM_k^{-1} )mod M, M^{-1}_i为M_i模m_i的逆元, M_i*mi=M
$$

https://vjudge.net/problem/POJ-1006 求同余方程

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<cstdio>
#include<iostream>
using namespace std;

void e_gcd(int a, int b, int &d, int &x, int &y){
    if(!b){
        d = a; x = 1; y = 0;
        return ;
    }
    e_gcd(b, a%b, d, y, x);
    y -= x*(a/b);
}
//中国剩余定理
int CRT(int a[], int m[], int n){
    int M = 1;
    int ans = 0;
    for(int i = 0; i < n; i++)M *= m[i];
    for(int i = 0; i < n; i++){
        int x,y,d;
        int Mi = M/m[i];
        e_gcd(Mi, m[i], d, x, y);
        ans = (ans + Mi*x*a[i])%M;
    }
    if(ans<0)ans+= M;
    return ans;
}
int a[10],m[10];
int main(){
    int a1,a2,a3,cha,t=0;
    m[0]=23;m[1]=28;m[2]=33;
    while(~scanf("%d%d%d%d",&a1,&a2,&a3,&cha)){
        if(a1==-1)
        a[0] = a1;a[1] = a2; a[2] = a3;
        int ans = CRT(a,m,3);
        ans -= cha;
        if(ans<=0)ans+=m[0]*m[1]*m[2];
        printf("Case %d: the next triple peak occurs in %d days.\n",++t,ans);
    }
}

对于普通中国剩余定理要求的$m_1,m_2,…,m_k$互素.但如果发生不互素时,需要采用两两合并.

如$x = a_1 + m_1 x_1 , x = a_2 + m_2 x_2$, 连立方程有$a_1 + m_1x_1 = a_2 + m_2x_2$,

利用e_gcd()算出$x_1的最小正整数解,再带入 x = a_1 + m_1 x_1$

$y \equiv x (mod \ lcm(m_1, m_2))$

一直合并下去.这题数据范围其实很大,所以ll,才能过

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;

ll a[1000],m[1000];

void e_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a;x=1;y=0;
        return ;
    }
    e_gcd(b, a%b, d, y, x);
    y -= (a/b)*x;
}

ll pCRT(ll a[], ll m[], ll n){
    ll M = 1;
    ll ans = 0;
    ll d,x,y;
    for(int i = 0; i < n; i++)M*=m[i];
    for(int i = 0; i < n; i++){
        ll Mi = M/m[i];
        e_gcd(Mi, m[i], d, x, y);
        ans = (ans + x*a[i]*Mi)%M;
    }
    return ans;
}

ll gcd(ll a, ll b){
    return b?gcd(b,a%b):a;
}

ll Inv(ll a, ll b){
    ll d,x,y;
    e_gcd(a,b,d,x,y);
    if(d!=1)return -1;
    return (x%b+b)%b;
}

bool merger(ll a1, ll m1, ll a2, ll m2, ll &a3, ll &m3){
    ll d = gcd(m1,m2);
    ll c = a2 - a1;
    if(c%d)return false;
    c = (c%m2+m2)%m2;
    m1 /= d;m2 /= d;
    c /= d;
    c *= Inv(m1,m2);//实际是在求解
    c %= m2;
    c *= m1*d;//变为x
    c += a1;

    m3 = m1*m2*d;
    a3 = (c%m3+m3)%m3;
    return true;
}

ll mCRT(ll a[], ll m[], ll n){
    ll a0 = a[0];
    ll m0 = m[0];
    for(int i = 1; i < n; i++){
        ll tempa = a[i];
        ll tempm = m[i];
        ll ansa,ansm;
        if(!merger(a0,m0,tempa, tempm, ansa, ansm))
            return -1;
        a0 = ansa;
        m0 = ansm;
    }
    return (a0%m0+m0)%m0;
}

int main(void ){
    ll n;
    while(~scanf("%lld",&n)){
        for(int i = 0; i < n; i++){scanf("%lld%lld",&m[i],&a[i]);}
        ll ans = mCRT(a,m,n);
        printf("%lld\n",ans);
    }
}

CRT 习题:

$$x \equiv \ x_1(\% \ \ mod1)\ x \equiv \ x_2(\% \ \ mod2)$$

H - Mysterious For HDU - 4373

先将题目转化成数学, 计算时可以找规律最后发现是组合数的乘积,考虑卢卡斯定理,但由于给的mod是一个合数,将这个合数分解为2个质数,然后用CRT就可以解决了.

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
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
const ll p1 = 97;
const ll p2 = 3761599;
const ll mod = p1*p2;
ll fac1[p1+5],fac2[p2+5];
int pos[18];
ll inv1,inv2;

ll power(ll a, ll b, ll mod){
    a%=mod;
    ll ans = 1;
    while(b){
        if(b&1)ans = ans*a%mod;
        a = a * a %mod;
        b >>=1;
    }
    return ans;
}

void init(){
    fac1[0]=fac2[0]=1;
    for(int i = 1; i < p1; i++){
        fac1[i] = fac1[i-1]*i%p1;
    }
    for(int i = 1; i < p2; i++){
        fac2[i] = fac2[i-1]*i%p2;
    }
}

void e_gcd(ll a, ll b, ll &d, ll &x, ll &y){
    if(!b){
        d = a; x = 1; y = 0;
        return ;
    }
    e_gcd(b, a%b, d, y, x);
    y -= (a/b)*x;
}

ll inv(ll a, ll b){
    ll d,x,y;
    e_gcd(a, b, d, x, y);
    if(d!=1)return -1;
    return (x%b+b)%b;
}

ll C(int n, int m, int mod){
    if(m>n)return 0;
    ll a,b,c;
    if(mod == p1){
        a = fac1[n], b = fac1[n-m], c = fac1[m];
    }else{
        a = fac2[n], b = fac2[n-m], c = fac2[m];
    }
    //return a*inv(b*c%mod, mod)%mod; //欧几里得
    return a*power(b*c%mod, mod-2, mod)%mod;
}

ll Lucas(int n, int m, int mod){
    if(m == 0)return 1;
    return C(n%mod, m%mod, mod)*Lucas(n/mod, m/mod, mod)%mod;
}

ll CRT(ll a[], ll m[], int n){
    ll M = 1;
    ll ans = 0;
    for(int i = 0; i < n; i++)M *= m[i];
    for(int i = 0; i < n; i++){
        ll x,y,d;
        ll Mi = M/m[i];
        e_gcd(Mi, m[i], d, x, y);
        ans = (ans + Mi*x*a[i])%M;
    }
    if(ans<0)ans+= M;
    return ans;
}

ll a[3],m[3];
int data[30];
ll n,mm,num;
int main(){
    init();
    int t=0,T;scanf("%d",&T);
    m[0] = p1;m[1] = p2;
    while(t++<T){
        scanf("%lld%lld%lld",&n,&mm,&num);
        for(int i = 0; i < num; i++){
            scanf("%d",&data[i]);
        }
        data[num++] = mm;
        ll ans = 1;
        //cout << "first"<<endl;
        for(int i = 1; i < num; i++){
            //cout << i<< endl;
            int k = data[i] - data[i-1];
            //if(k==1)continue;
            //cout << "n+k-1 : "<<n+k-1<<" "<<p1<<" "<<p2<< endl;
            a[0] = Lucas(n+k-1,k,p1);
            a[1] = Lucas(n+k-1,k,p2);
            //cout << a[0] <<":"<< a[1]<<endl;
            ans = ans*CRT(a,m,2)%mod;
        }
        //cout << "yes";
        //ans = ans*power(n, num-1, mod)%mod;
        printf("Case #%d: %lld\n",t,ans);
        //cout << flush;
    }
    return 0;
}

反素数

记f(n)为n的约数个数.若对于所有的i,0<i<n,f(i)<f(n).则称n为反素数.

性质: 1. 反素数的所有质因子是从2开始的,且$$n = 2^{t_1}3^{t_2}… , 且满足t_1 >= t_2$$

例题: 求最小的一个数使其因数个数为n.

对每个数的所有因子用搜索.

A - Number With The Given Amount Of Divisors CodeForces - 27E (dfs+反素数)

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
#include<cstdio>
#include<iostream>
#define  ll unsigned long long
const ll inf = ~0;
using namespace std;
ll ans ;
bool judge[1000];
int prime[1000];
int n,cnt=0;

void dfs(int depth, ll tmp, int num){
    if(num > n || depth>=cnt)return;
    if(num == n && ans>tmp){
        ans = tmp;
        return;
    }
    for(int i= 1; i <= 63; i++){
        if(ans/prime[depth]<tmp || num*(i+1)>n)break;
        dfs(depth+1, tmp*=prime[depth], num*(i+1));
    }
}

int main(){
        for(int i = 2; i<100; i++) {
        if(!judge[i]) {
            for(int j = i+i; j<100; j+=i) {
                judge[j] = 1;
            }
            prime[cnt++] = i;
        }
    }
    while(~scanf("%d",&n)){
        ans = inf;
        dfs(0,1,1);
        printf("%llu\n", ans);
    }
}

B - The Most Complex Number URAL - 1748

利用反素数性质来剪枝. 算1-n因数最大的数.

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
56
57
58
59
60
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
const int maxn = 100;

int judge[maxn],phi[maxn],prime[maxn],mu[maxn];
int tot = 0;
void init(){
    mu[1] = 1;
    for(int i = 2; i < maxn; i++){
        if(!judge[i]){
            prime[tot++]=i;
            mu[i] = -1;
            phi[i] = i-1;
        }
        for(int j = 0; j < tot; j++){
            if(i*prime[j]>=maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j]==0){
                mu[i*prime[j]]=0;
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }else{
                mu[i*prime[j]]= -mu[i];
                phi[i*prime[j]] = phi[i]*(prime[j]-1);
            }
        }
    }
}

ll a,b;
ll n;
void dfs(int depth, ll ansa, int ansb, int limit){
    if(depth>=tot-1)return;
    if(ansa>n)return;
    if(ansb > b|| ((ansb == b) && a>ansa)){
        a = ansa;
        b = ansb;
    }
    ll temp = ansa;
    for(ll i = 1;depth < tot && i <= limit; i++){
        if(temp > n/prime[depth])break;
        temp *= prime[depth];
        dfs(depth+1, temp, ansb*(i+1), i);
    }
    return ;
}

int main(){
    init();int t = 0,T;scanf("%d",&T);
    while(T--){
        a = 0,b=0;
        scanf("%lld",&n);
        dfs(0,1,1, 63);
        printf("%lld %lld\n",a,b);
    }
    return 0;
}

D - 反素数 HDU - 2521

求[a,b]区间的内的素因数最大的数.可能会出现没有反素数的情况,由于数据小,把limit去掉,改一下就可以了.

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
56
57
58

#include<cstdio>
#include<iostream>
#define maxn 200
#define ll long long
using namespace  std;

int prime[maxn],judge[maxn],mu[maxn],phi[maxn];
int tot=0;
void init(){
    mu[1]=  1;
    for(int i = 2; i <maxn; i++){
        if(!judge[i]){
            mu[i]=-1;
            prime[tot++]=i;
            phi[i] = i-1;
        }
        for(int j = 0; j <tot; j++){
            if(i*prime[j]>=maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j]==0){
                mu[i*prime[j]] = 0;
                phi[i*prime[j]] =phi[i] *prime[j];
                break;
            }else{
                mu[i*prime[j]] = -mu[i];
                phi[i*prime[j]] = phi[i]*(prime[j]-1);
            }
        }
    }
}
ll ans,mi;
int a,b;
void dfs(int depth, ll ansa, int ansb, int limit){
    if(depth>=tot)return;
    if(ansa>b)return ;
    if(((mi<ansb) || (mi == ansb && ansa < ans)) && ansa>=a){
        ans = ansa;
        mi = ansb;
    }
    ll temp = ansa;
    for(int i = 0; i <= limit; i++){
        dfs(depth+1, temp, ansb*(i+1), limit);
        if(temp > b/prime[depth])break;
        temp *= prime[depth];
    }
}

int main(){
    int t;scanf("%d",&t);
    init();
    while(t--){
        ans = mi = 0;
        scanf("%d%d",&a,&b);
        dfs(0,1,1,63);
        printf("%lld\n",ans);
    }
}

E - 小明系列故事——未知剩余系](https://vjudge.net/problem/HDU-4542) HDU - 4542(预处理+剪枝)

需要强大的剪枝.,这里的预处理写的很好,先算出的d[i]为非因数的个数,然后和下标做了一个对换.

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
56
57
58
59
60
61
62
63
64
65
66
#include<iostream>
#include<cstdio>
#define maxn 50000
#define maxnn 70
#define ll unsigned long long
using namespace std;

int prime[] = {2,3,5,7,11,13,17,19,23,29,31,37,41,47,53};
int d[maxn];
void create_table(){
    for(int i = 1; i < maxn; i++){
        d[i] = i;
    }
    for(int i = 1; i < maxn; i++){
        for(int j = i; j <maxn; j+=i){
            //算非因子个数
            d[j]--;
        }
        // 互换.
        if(!d[d[i]])
            d[d[i]] = i;
        d[i] = 0;
    }
}

ll ans;
ll pos = 4611686018427387904;
int flag;
int type,k;
void dfs(int depth, ll ansa, int ansb, int limit){
    if(ansb > k)return ;
    if(ansb == k && ansa<ans){
        ans = ansa;
        return ;
    }
    if(depth>15)return;
    for(int i = 1; i <= limit; i++){
        if(ansa > pos/prime[depth] || ansb*(i+1)>k){break;}
        ansa*=prime[depth];
        if(k%(ansb*(i+1))==0)
        dfs(depth+1, ansa, ansb*(i+1), i);
    }
}

int main(){
    create_table();
    int T,t=0;scanf("%d",&T);
    while(t++<T){
        scanf("%d%d",&type,&k);
        ans = flag = 0;
        if(type){
            if(d[k])
                printf("Case %d: %d\n",t,d[k]);
            else printf("Case %d: Illegal\n",t);
        }else{
            ans = ~0ull;
            dfs(0,1,1,63);
            if(ans > pos){
                printf("Case %d: INF\n",t);
            }else{
                printf("Case %d: %llu\n",t,ans);
            }
        }
    }
    return 0;
}

模板

欧拉函数/莫比乌斯/质数

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
bool judge[maxn];
int prime[maxn],mu[maxn],phi[maxn];
int tot=0;
void init(){
    memset(judge, 0 , sizeof judge);
    mu[1] = 1;
    for(int i = 2; i < maxn; i++){
        if(!judge[i]){
            prime[tot++]=i;
            mu[i] = -1;
            phi[i] = i-1;
        }
        for(int j = 0; j < tot; j++){
            if(i*prime[j]>=maxn)break;
            judge[i*prime[j]] = 1;
            if(i%prime[j] == 0){
                mu[i*prime[j]] = 0;
                phi[i*prime[j]] = phi[i]*prime[j];
                break;
            }else{
                mu[i*prime[j]] = -mu[i];
                phi[i*prime[j]]=phi[i]*(prime[j]-1);
            }
        }
    }
}

本文标题:Acdreamer博客数论学习(2)

文章作者:呼哧

发布时间:2017-08-05, 01:40:42

最后更新:2018-08-04, 02:45:30

原始链接:http://hu-chi.github.io/2017/08/05/acm/Acdreamer博客数论学习(2)/

许可协议: "署名-非商用-相同方式共享 4.0" 转载请保留原文链接及作者。

文章目录
  1. 1. Acdreamer 博客学习(2)
  2. 2. Day Three
    1. 2.1. 组合数取模/Lucas
    2. 2.2. Lucas习题:
    3. 2.3. DP?HDU - 3944
    4. 2.4. Xiao Ming’s Hope HDU - 4349
    5. 2.5. CRT(中国剩余定理)
    6. 2.6. CRT 习题:
    7. 2.7. H - Mysterious For HDU - 4373
    8. 2.8. 反素数
    9. 2.9. A - Number With The Given Amount Of Divisors CodeForces - 27E (dfs+反素数)
    10. 2.10. B - The Most Complex Number URAL - 1748
    11. 2.11. D - 反素数 HDU - 2521
    12. 2.12. E - 小明系列故事——未知剩余系](https://vjudge.net/problem/HDU-4542) HDU - 4542(预处理+剪枝)
    13. 2.13. 模板
      1. 2.13.1. 欧拉函数/莫比乌斯/质数
|