soj 3137 Simple Computing 容斥原理 hdu 1796 How many integers can you find

╰+哭是因爲堅強的太久メ 2021-12-20 16:25 194阅读 0赞

/*
     * hdu1796.c
     *
     *  Created on: 2011-10-3
     *      Author: bjfuwangzhu
    */
    #include<stdio.h>
    #define LL long long
    #define nmax 11
    int num[nmax], nlen;
    LL res;
    int gcd(int a, int b) {
        
    return b == 0 ? a : gcd(b, a % b);
    }
    void dfs(int start, int c, int lcm, int n) {
        
    int i;
        lcm = lcm / gcd(lcm, num[start]) * num[start];
    if (c & 1) {
        
            res += n / lcm;
        } else {
        
            res -= n / lcm;
        }
    for (i = start + 1; i < nlen; i++) {
        
            dfs(i, c + 1, lcm, n);
        }
    }
    int main() {
        
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
    #endif
    int n, m, mm, i, j;
    while (~scanf("%d %d", &n, &m)) {
        
    for (i = 0, nlen = 0; i < m; i++) {
        
                scanf("%d", &mm);
    if (mm > 0 && mm < n) {
        
                    num[nlen++] = mm;
                }
            }
            res = 0;
    for (j = 0; j < nlen; j++) {
        
                dfs(j, 1, num[j], n - 1);
            }
            printf("%lld\n", res);
        }
    return 0;
    }

/*
     * soj3137.c
     *
     *  Created on: 2011-10-10
     *      Author: bjfuwangzhu
    */
    
    #include<stdio.h>
    #define LL long long
    #define nmax 11
    int num[nmax];
    int n, m, res, flag;
    int gcd(int a, int b) {
        
    return b == 0 ? a : gcd(b, a % b);
    }
    void dfs(int start, int lcm) {
        
        LL temp;
    if (start == n) {
        
    if (flag & 1) {
        
                res += m / lcm;
            } else if (flag > 0) {
        
                res -= m / lcm;
            }
    return;
        }
        temp = (LL) lcm;
        temp = temp / gcd(lcm, num[start]) * num[start];
        flag++;
    if (temp <= m) {
        
            dfs(start + 1, temp);
        }
        flag--;
        dfs(start + 1, lcm);
    }
    int main() {
        
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
    #endif
    int t, i;
        scanf("%d", &t);
    while (t--) {
        
            scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        
                scanf("%d", num + i);
            }
            res = 0, flag = 0;
            dfs(0, 1);
            printf("%d\n", res);
        }
    return 0;
    }

/*
     * soj3137.c
     *
     *  Created on: 2011-10-10
     *      Author: bjfuwangzhu
    */
    
    #include<stdio.h>
    #define LL long long
    #define nmax 11
    int num[nmax];
    int n, m, res;
    int gcd(int a, int b) {
        
    return b == 0 ? a : gcd(b, a % b);
    }
    void dfs(int i, LL lcm, int flag) {
        
    int j;
        lcm = lcm / gcd(lcm, num[i]) * num[i];
    if (flag & 1) {
        
            res += m / lcm;
        } else {
        
            res -= m / lcm;
        }
        flag++;
    for (j = i + 1; j < n; j++) {
        
            dfs(j, lcm, flag);
        }
    }
    int main() {
        
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
    #endif
    int t, i;
        scanf("%d", &t);
    while (t--) {
        
            scanf("%d %d", &n, &m);
    for (i = 0; i < n; i++) {
        
                scanf("%d", num + i);
            }
            res = 0;
    for (i = 0; i < n; i++) {
        
                dfs(i, 1, 1);
            }
            printf("%d\n", res);
        }
    return 0;
    }

hdu 1796 How many integers can you find

/*
     * hdu1796.c
     *
     *  Created on: 2011-10-3
     *      Author: bjfuwangzhu
    */
    #include<stdio.h>
    #define LL long long
    #define nmax 11
    int num[nmax], nlen, flag;
    LL res;
    int gcd(int a, int b) {
        
    return b == 0 ? a : gcd(b, a % b);
    }
    void dfs(int start, int lcm, int n) {
        
        LL temp;
    if (start == nlen) {
        
    if (flag & 1) {
        
                res += n / lcm;
            } else if (flag > 0) {
        
                res -= n / lcm;
            }
    return;
        }
        temp = (LL) lcm;
        temp = temp / gcd(lcm, num[start]) * num[start];
        flag++;
    if (temp <= n) {
        
            dfs(start + 1, temp, n);
        }
        flag--;
        dfs(start + 1, lcm, n);
    }
    int main() {
        
    #ifndef ONLINE_JUDGE
        freopen("data.in", "r", stdin);
    #endif
    int n, m, mm, i;
    while (~scanf("%d %d", &n, &m)) {
        
    for (i = 0, nlen = 0; i < m; i++) {
        
                scanf("%d", &mm);
    if (mm > 0 && mm < n) {
        
                    num[nlen++] = mm;
                }
            }
            res = 0, flag = 0;
            dfs(0, 1, n - 1);
            printf("%lld\n", res);
        }
    return 0;
    }

转载于:https://www.cnblogs.com/xiaoxian1369/archive/2011/10/10/2205804.html