互质定理

  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*, 则 a^n≡b^n(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;
}