同余定理简单应用 - poj2769 - hdu 1021 - hdu 2035

同余问题

基本定理：

若a,b,c,d是整数,m是正整数, a = b(mod m), c = d(mod m)

1. a+c = b+c(mod m)
2. ac = bc(mod m)
3. ax+cy = bx+dy(mod m) -同余式可以相加
4. ac = bd(mod m) -同余式可以相乘
5. a^n = b^n(mod m)
6. f(a) = f(b)(mod m)

7. if a = b(mod m) and d|m then a = b(mod d)

   eg: 320 = 20(mod 100) and d = 50 then 320 = 20(mod 50)
   and d = 10 then 320 = 20(mod 10)

8. if a = b(mod m) then (a,m) = (b,m)

   eg: 17 = 2(mod 5) ==> 1 = 1

9. if ac = bc(mod m) and (c,m) = d then a = b(mod m/d)

   eg: 320 = 20(mod 100) ==> 16 = 1(mod 5)
10. (a+b)mod m = (a mod m + b mod m)mod m
11. (a * b)mod m = (a mod m * b mod m) mod m

12. (a^n)mod m = (a mod m)^n mod m

同余定理应用

pku 2769

需要加一个优化，否则会超时

复制代码#include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> using namespace std; int people[330]; bool vis[1000010]; bool judge[1000010]; int main() { int cas; scanf("%d",&cas); int num; while(cas--) { scanf("%d",&num); memset(judge,0,sizeof(judge)); for(int i = 0 ; i < num ; i++) scanf("%d",&people[i]); //剪枝 for(int i = 0 ; i < num ; i++) for(int j = 0 ; j < num ; j++) judge[abs(people[i]-people[j])] = 1; //枚举 int k; for(k = 1 ;; k++) { if(!judge[k]) { bool isfind = true; memset(vis,0,sizeof(vis)); for(int i = 0 ; i < num ; i++) { if(vis[people[i]%k]) { isfind = false; break; } vis[people[i]%k] = 1; } if(isfind) { printf("%dn",k); break; } } } } 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
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 <cstdio>
#include <cstring>
#include <cstdlib>
#include <cmath>

using namespace std;

int people[330];
bool vis[1000010];
bool judge[1000010];

int main()
{
    int cas;
    scanf("%d",&cas);
    int num;
    while(cas--)
    {
        scanf("%d",&num);
        memset(judge,0,sizeof(judge));
        for(int i = 0 ; i < num ; i++)
            scanf("%d",&people[i]);
        //剪枝
        for(int i = 0 ; i < num ; i++)
            for(int j = 0 ; j < num ; j++)
                judge[abs(people[i]-people[j])] = 1;
        //枚举
        int k;
        for(k = 1 ;; k++)
        {
            if(!judge[k])
            {
                bool isfind = true;
                memset(vis,0,sizeof(vis));
                for(int i = 0 ; i < num ; i++)
                {
                    if(vis[people[i]%k])
                    {
                        isfind = false;
                        break;
                    }
                    vis[people[i]%k] = 1;
                }
                if(isfind)
                {
                    printf("%dn",k);
                    break;
                }
            }
        }
    }
    return 0;
}

hdu 1021 Fibonacci Again

复制代码#include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; int F[1000000+10]; void process() { memset(F,0,sizeof(F)); F[0] = 7%3, F[1] = 11%3; for(int i = 2 ; i < 1000000 ; i++) { F[i] = (F[i-1]%3+F[i-2]%3)%3; } } int main() { process(); int n; while(cin >> n) { if(F[n]) cout << "no" << endl; else cout << "yes" << endl; } 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
27
28
29
30
31
32
33
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;
int F[1000000+10];

void process()
{
    memset(F,0,sizeof(F));
    F[0] = 7%3, F[1] = 11%3;
    for(int i = 2 ; i < 1000000 ; i++)
    {
        F[i] = (F[i-1]%3+F[i-2]%3)%3;
    }
}

int main()
{
    process();
    int n;
    while(cin >> n)
    {
        if(F[n])
            cout << "no" << endl;
        else
            cout << "yes" << endl;
    }
    return 0;
}

hdu 2035 人见人爱A^B

复制代码#include <iostream> #include <cstdio> #include <cmath> #include <cstdlib> #include <cstring> using namespace std; int F[1000000+10]; int process(int a, int b) { int ans = a; b--; while(b--) { ans = (ans%1000 * a%1000)%1000; } return ans; } int main() { int a, b; while(cin >> a >> b && a) { cout << process(a,b) << endl; } 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
27
28
29
30
31
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <cstring>

using namespace std;
int F[1000000+10];

int process(int a, int b)
{
    int ans = a;
    b--;
    while(b--)
    {
        ans = (ans%1000 * a%1000)%1000;
    }
    return ans;
}

int main()
{
    int a, b;
    while(cin >> a >> b && a)
    {
          cout << process(a,b) << endl;
    }

    return 0;
}