数论基础一

关于这段时间对数论基础的一个简短小更新…
随手配图


emmmmmmm,是这样,前段时间集训队教矩阵快速幂,怎么说呢 没大懂,就登上计蒜客把数论基础这块学了,但是计蒜客模块还是很多的,前面都是之前学过的一些东西,就先来写一下关于这方面的,算是一个小复习,也是对矩阵快速幂的学习的一个准备吧,我要好好刷题。。。。漏了好多了,真是罪过…..

OK,进入正文:

先是关于一个整除和余数的简单介绍吧,上图:

RT,其实这些比较明显啦 后面那两个余数还是多熟悉一下就OK

emmmm然后介绍正式的点的了
gcd与lcm和欧几里得算法:

代码块:

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

其实这个函数会就行了 因为algorithm头文件有__gcd()可以直接调用(注意是两个_)

上个水题?…(真水的不行。。。我也不知道我为什么放上来…

计蒜客:两仪剑法(。。。这标题。

问题描述
两仪剑法是武当派武功的高级功夫,且必须 2 个人配合使用威力才大。同时该剑法招数变化太快、太多。设武当弟子甲招数变化周期为 n,武当弟子乙招数变化周期为 m,两弟子同时使用该剑法,当 2 人恰好同时达到招数变化周期结束时,威力最大,此时能将邪教妖人置于死地。请你计算威力最大时,每人用了多少招?
输入格式
首先输入一个 t(t<100000) 表示测试组数。
接下来 t组输入,每组输入 2 个数n,m(1≤n,m≤1000000000)。
输出格式
对于每组输出,输出用了多少招数。
样例输入
3
2 3
8 9
4 8

样例输出
6
72
8

AC代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <iostream>
#include <algorithm>
#define ll long long
using namespace std;
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
ll n,m;
ll wyh;
cin>>n>>m;
wyh=n*m;
cout<<wyh/__gcd(n,m)<<endl;
}
return 0;
}

(没脸见人

计蒜客:取石子游戏

问题描述
蒜头君和花椰妹在玩一个游戏,他们在地上将 n 颗石子排成一排,编号为 1 到 n。开始时,蒜头君随机取出了 2 颗石子扔掉,假设蒜头君取出的 2 颗石子的编号为 a, b。游戏规则如下,蒜头君和花椰妹 2 人轮流取石子,每次取石子,假设某人取出的石子编号为 i,那么必须要找到一对 j, k 满足 i=j−k 或者 i=j+k ,并且编号为 j,k 的石子已经被取出了,如果谁先不能取石子了,则视为输了。蒜头君比较绅士,让花椰妹先手。
输入格式
第一行输入一个整数 t(1≤t≤500),表示蒜头君和花椰妹进行了 t 局游戏。
对于每局游戏,输入 3 个整数 n(2≤n≤20000),a,b(1≤a,b≤n),保证 a,b 不相等。
输出格式
如果蒜头君赢了游戏,输出一行suantou,如果花椰妹赢了,输入一行huaye。
样例输入
5
8 6 8
9 6 8
10 6 8
11 6 8
12 6 8
样例输出
suantou
suantou
huaye
huaye
suantou
AC 代码:

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 <iostream>
using namespace std;
int gcd(int a,int b)
{
if(b==0)return a;
else return gcd(b,a%b);
}
int main()
{
ios::sync_with_stdio(false);
int t;
cin>>t;
while(t--)
{
int n,a,b;
int ans=0;
cin>>n>>a>>b;
if(a>b){
int temp=a;
a=b;
b=temp;
}
//cout<<gcd(a,b)<<endl;
for(int i=1;i<=n;i++)
{
if(i==a||i==b)ans--;
if(i%gcd(a,b)==0)ans++;
}
if(ans%2==0)cout<<"suantou"<<endl;
else cout<<"huaye"<<endl;
}
return 0;
}

这个也就是gcd的稍微变形吧….
质数筛选
挑选出质数大家当然都会:最简单的从2枚举到n-1;以此判断每个数是不是;但是有么有更好的方法呢?
仔细想想:如果对于一个数i来说,那么i2、i3、….i*n都不是质数。所以有了这样的方法

1
2
3
4
5
6
7
8
for (int i = 2; i <= n; ++i) {
is_prime[i] = 1;
}
for (int i = 2; i <= n; ++i) {
for (int j = i * 2; j <= n; j += i) {
is_prime[j] = 0;
}
}

如此便筛选出了n以内的素数,先是将2-n的所有数看成素数,然后对一个j一次将j的整数倍数数全部变成非素数。
总时间复杂度为:O(NlgN)
然后还是可以优化的,因为每个合数(非素数)必有一个质因子

1
2
3
4
5
6
7
8
9
10
for (int i = 2; i <= n; ++i) {
is_prime[i] = 1;
}
for (int i = 2; i * i <= n; ++i) {
if (is_prime[i]) {
for (int j = i * i; j <= n; j +=i) {
is_prime[j] = 0;
}
}
}

看上去其实和上面的差别不大,就是把对于一个被看成素数的数,从平方开始变为0

计蒜客:蒜头君的猜想

问题描述
有一天蒜头君突发奇想,他有一个猜想,任意一个大于 2 的偶数好像总能写成 2 个质数的和。蒜头君查了资料,发现这个猜想很早就被一个叫哥德巴赫的人提出来了,称为哥德巴赫猜想。目前还没有证明这个猜想的正确性。蒜头君告诉你一个整数 n ,让你用这个数去验证。注意 1 不是质数。
输入格式
输入一个偶数 n(2

//不得不吐槽…为什么计蒜客的题目复制不了,从别人的博客粘贴来的 将就着看吧…
AC CODE:

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 <iostream>
using namespace std;
const int maxn=8000005;
bool is_prime[maxn];
void init()
{
for(int i=2;i<maxn;i++)
is_prime[i]=1;
for(int i=2;i*i<maxn;i++)
{
if(is_prime[i])
{
for(int j=i*i;j<maxn;j+=i)
is_prime[j]=0;
}
}

}
int main()
{
ios::sync_with_stdio(false);
init();
int n;
cin>>n;
int ans=0;
for(int i=2;i<=n/2;i++)
{
if(is_prime[i]&&is_prime[n-i])
ans++;
}
cout<<ans<<endl;
return 0;
}

不想解释什么了
计蒜客:素数距离
问题描述
蒜头君请你求出区间 [l,r] 上距离最近的相邻的素数对和距离最远的相邻的素数对。3,5 是相邻的素数,2,5 不是相邻的素数。距离定义为 2 个素数的差的绝对值。比如 5,7 距离为 2。
输入格式
输入 2 个整数l,r(1≤l≤r≤8000000)
输出格式
如果 a,b(a< b) 是距离最近的素数对,c,d(c< d) 是距离最远的素数对,按照如下格式输出a,b are closest, c,d are most distant. 。如果最近或者最远有多对,输出 a 和 c 最小的。如果没有相邻是素数对,输出There are no adjacent primes.。
样例输入
3 10
样例输出
3,5 are closest, 3,5 are most distant.

这个题算是有点变化了…用一个数组保存素数就行 再用个数组保存最近的素数之间的差
//3 10
//3 4 5 6 7 8 9 10
//sushu: 3 5 7
//wyh: 1-3 2-5 3-7
//minlen=2 maxlen=2

AC CODE:

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
#include <iostream>
#include <cstring>
#include <bits/stdc++.h>
#include <cstdio>
using namespace std;
const int maxn=8000005;
bool is_prime[maxn];
int wyh[maxn];
void init()
{
for(int i=2;i<maxn;i++)is_prime[i]=1;

for(int i=2;i*i<maxn;i++)
{
if(is_prime[i]){
for(int j=i*i;j<maxn;j+=i)is_prime[j]=0;
}
}
}
int main()
{
ios::sync_with_stdio(false);
init();
int n,m;
cin>>n>>m;
int min_len,max_len;
int ans=0;
for(int i=n;i<=m;i++)
{
if(is_prime[i]==1)wyh[++ans]=i;
}
if(ans==0||ans==1){
cout<<"There are no adjacent primes."<<endl;
return 0;
}
min_len=wyh[2]-wyh[1];//2
max_len=wyh[2]-wyh[1];//2
int cnt,cntt;
cnt=1;
cntt=1;
for(int i=1;i<ans;i++)
{
if(min_len>wyh[i+1]-wyh[i]){
cnt=i;
min_len=wyh[i+1]-wyh[i];
}
if(max_len<wyh[i+1]-wyh[i]){
cntt=i;
max_len=wyh[i+1]-wyh[i];
}
}
cout<<wyh[cnt]<<","<<wyh[cnt+1]<<" are closest, ";
cout<<wyh[cntt]<<","<<wyh[cntt+1]<<" are most distant."<<endl;
return 0;
}

欧拉函数与积性函数

这部分开始就比较有东西了…还是我太菜了
上一些关于理论的东西先看看:

代码实现:

1
2
3
4
5
6
7
8
9
int res = n;
for (int i = 2; i * i <= n; ++i) {
if (n % i == 0) {
res = res / i * (i - 1); //先进行除法是为了防止中间数据溢出
while (n % i == 0) {
n /= i;
}
}
}

这一块还是要在理解理解 主要是中间这步
防止中间数据洗出没看懂 欢迎评论指导

其实有道题…但是不想上,模板的不行
上一下这题
计蒜客:质数原根

问题描述
如果一个数 x(0< x< p),满足集合 {xi%p∣1≤i< p} 等价于集合 {1,⋯,p−1},则我们称 x 为质数 p 的一个原根。例如,假设 p 为 3,2 的各项幂对 3 取余的结果为 2,1,则 2 为质数 p 的一个原根。
现在已知一个质数 p,求质数 p 的原根个数。
输入格式
输入有多组数据,不超过100行。
每组数据输入一行,输入一个质数 p(3≤p≤100,000)。
输出格式
对于每组测试数据,输出一行,输出质数 p 的原根个数。
样例输入
11
13
17
样例输出
4
4
8

老实说吧,这题一开始我是想望欧拉上靠,但是楞没理清楚逻辑,然后捏,中规中矩来了一把错误代码(我觉得逻辑上好像没啥问题,欢迎指正,那个结果就瞎几把出啥0啊1啊啥的肯定错,然后看计蒜客网站给的小提示想明白的,就是p-1的欧拉函数值,虽然我也不知道咋来的,但是打表确实这样:
WA code:

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 <iostream>
#include <cstring>
using namespace std;
const int maxn=1e5+1;
bool is_prime[maxn];
int skr[maxn];
void init()
{
for(int i=2;i<maxn;i++)
is_prime[i]=1;
for(int i=2;i*i<=maxn;i++)
{
if(is_prime[i]){
for(int j=i*i;j<=maxn;j+=i)
is_prime[i]=0;
}
}
}
long long pow(int a,int b,int mod)
{
long long res=1;
while(b>0){
if(b&1)res=res*a%mod;
a=a*a%mod;
b>>=1;
}
return res;
}
int main()
{
ios::sync_with_stdio(false);
init();
int n;
int ans=0;
while(cin>>n)
{
memset(skr,0,sizeof(skr));
bool wyh=false;
for(int i=1;i<n;i++)
{
for(int j=1;j<n;j++){
skr[pow(i,j)%n]++;
}
for(int k=1;k<n;k++)
{
if(skr[k]>1)
{
wyh=true;
break;
}
}
if(!wyh)ans++;
memset(skr,0,sizeof(skr));
}
cout<<ans<<endl;
}
return 0;
}

再上后来写的AC CODE:

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 <iostream>
using namespace std;
const int maxn=1e5;
int s[maxn];
int erler(int n)
{
int ans=n;
for(int i=2;i*i<=maxn;i++)
{
if(n%i==0)
{
ans=ans/i*(i-1);
while(n%i==0){
n/=i;
}
}
}
if(n>1)
{
ans=ans/n*(n-1);
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
int p;
while(cin>>p)
{
cout<<erler(p-1)<<endl;
}
return 0;
}

扩展欧几里得
这部分早在上学期就讲过的,只是现在来看还是有不懂的地方(囧

方程:ax+by=gcd(a,b)=d
扩展欧几里得主要就是用来求这个方程的x,y(已知a,b时)
官方解读:(计蒜客官方啊

先更到这…我得去接人…明天写明天写,我明天一定学一定学矩阵快速幂

-------------本文结束感谢您的阅读-------------