基础数论

Posted on | In , | Visitors:

This is my blog.
（未完待续）
此篇为基础数论，贴上模版，难以理解的附上数学推导公式。

gcd 最大公约数

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

lcm 最小公倍数

1
2
3
int lcm(int a,int b){
    return a/gcd(a,b)*b;
}

欧拉函数

看到一篇不错的博客，讲解了一些欧拉函数的性质。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int eular(int x)
{
    int  res = x;
    for (int i =2; i *i<=x; i++)
    {
        if (x % i ==0)
        {
            res = res / i * (i -1);
            while (x % i ==0)
                x /= i; // 保证i一定是素数
        }
    }
    if (x > 1)
        res = res / x * (x -1);
    return res ;
}

容斥原理

假设只有三个，则为
\(p1+p2+p3-p1p2-p1p3-p2p3+p1p2*p3\)
可以知道总组合有\(2^n\)个，若该项个数为\(k\)，则系数为\( (-1)^(k+1) \)

例题

求大于x且与p互质的第k个数

思路

每个数的因子可以用筛法筛出来。然后就是二分查找ans，容斥原理计算ans内有多少个与p互质的数。至于大于x嘛，只需用容斥算出小于等于x的与p互质的数有多少个。

代码

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
#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll>v;
ll res(ll x){
    ll ans=0;
    int n=v.size();
    for(int i=0;i<(1<<n);i++){
        ll num=1;
        int tag=1;
        for(int j=0;j<n;j++){
            ll t=(i>>j);
            if(t&1){
                num*=v[j];
                tag*=-1;
            }
        }
        ans+=tag*(x/num);
    }
    return ans;
}
int main(){
    ios::sync_with_stdio(false);
    int T;scanf("%d",&T);
    while(T--){
        ll x,p,k;
        scanf("%lld%lld%lld",&x,&p,&k);
        for(ll i=2;i*i<=p;i++){
            if(p%i==0){
                vec.push_back(i);
                while((p%i)==0) p=p/i;
            }
        }
        if(p>1) vec.push_back(p);
        k += rec(x);
        
        ll l=1;ll r=1e9;
        ll ans=0;
        while(l<=r){
            ll mid=(l+r)>>1;
            if(res(mid)>=k){
                ans=mid;r=mid-1;
            }
            else l=mid+1;
        }
        
        printf("%lld\n",ans);
        v.clear();
    }
    return 0;
}

后记

数论比数学好玩！

转载请注明出处，谢谢。

愿 我是你的小太阳



买糖果去喽