互质和同余

互质定理

  1. GCD(a,b)=GCD(a,b-a*c)=GCD(a-b*c,b);
  2. 一定存在整数x、y,使得a*x+b*y=GCD(a,b);
  3. m*GCD(a,b)=GCD(a*m,b*m);
  4. 若GCD(a,b)=d,GCD(a/d,b/d)=1;
  5. m*LCM(a,b)=LCM(a*m,b*m);

同余定理

同余概念:对于两个数a、b,对m取余后相等,则称a和b同余。记作a≡b(mod m); 或者是对于两个数a、b,若m|(a-b) 则称a和b同余。

  1. 若a≡b(mod m),b≡c(mod m).则 a≡c(mod m);
  2. 若a≡b(mod m),c≡d(mod m).则 a±c≡b±d(mod m),a*c≡b*d(mod m);
  3. (a-b)%m=(a%m-b%m+m)%m;
  4. 若n|m,a≡b(mod m),则 a≡b(mod m);
  5. 若GCD(n,m)=1,a≡b(mod m),a≡b(mod n),则a≡b(mod n*m);
  6. a≡b(mod m), n∈n*, 则 an≡bn(mod m);
  7. a*c≡b*c(mod m),GCD(c,m)=d,则a≡b(mod m/d);

高精度模运算

其实就是很简单的,从高位到低位枚举,加上当前数字mod k,然后结果乘十,不停地做就行了。

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
#include<iostream>
#include<string>
using namespace std;
int n,mod,ans;
string s1;
int main()
{
cin>>s1>>mod;
n=s1.size()-1;
for(int i=0;i<=n;i++)
{
ans\*=10;
ans+=s1[i]-'0';
ans%=mod;
}
cout<<ans<<endl;
return 0;
}

放一道题来压压惊……

奶牛卧室

题目描述:

奶牛们有一个习惯,那就是根据自己的编号选择床号。如果一头奶牛编号是a,并且有0…k-1一共k张床,那么她就会选择a mod k号床作为她睡觉的地点。显然,2头牛不能睡在一张床上。那么给出一些奶牛的编号,请你为她们准备一间卧室,使得里面的床的个数最少。

输入:

  1. 第一行是奶牛的个数n(1<=n<=5000);
  2. 第2到第n+1行是每头奶牛的编号Si(1<=Si<=1000000)。

输出:

仅一行,是最少的床的数目。

题解:

这道题其实说白了就是对于任意一对编号(a,b),使得a%k!=b%k.
如果枚举k的话,可能会比较大,复杂度就是O(n*n*k)那么会超时的。

但是我们可以有一个结论,就是当(a-b)%k!=0时,a%k!=b%k.

这样的话我们就可以小小的优化一下了(真的只是小小的优化一下!)

结论证明:

当a%k!=b%k时。设x=a%k,y=b%k;
则x-y=a%k-b%k=(a-b)%k
因为x!=y,所以x-y!=0.
则(a-b)%k!=0.

突然觉得数论好有意思啊2333333333

我们有了这个结论之后就好办了,首先sort一下a[i],然后使用一个bool数组存储i是否为a-b中的一个,然后我们枚举k,每次用k的倍增来验证是否有(a-b)%k==0,如果发现有,说明这个k就是不成立的,继续枚举,一直找到为止。(k的范围就是从1到a[n])

复杂度*大约*是O(n*k),仅仅只是大约。

代码:

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
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<cstdio>
#include<cctype>
using namespace std;
int n,a[5001],p;
bool b[1000001];
inline int Read()
{
int F=true;
int This=false;
char ch=getchar();
while(!isdigit(ch))
{
if(ch=='-') F=-1;
ch=getchar();
}
while(isdigit(ch))
{
This=(This<<1)+(This<<3)+ch-'0';
ch=getchar();
}
return This\*F;
}
int main()
{
n=Read();
for(int i=1;i<=n;i++)
a[i]=Read();
sort(a+1,a+n+1);
for(int i=1;i<=n;i++)
for(int j=i+1;j<=n;j++)
b[a[j]-a[i]]=true;
for(int i=1;i<=a[n];i++)
{
bool Flag=false;
p=i;
while(p<=a[n])
{
if(b[p])
{
Flag=true;
break;
}
p+=i;
}
if(!Flag)
{
p=i;
break;
}
}
cout<<p<<endl;
return 0;
}