天天看点
返回

ACdream 简单数论 专题

A - ACdream运动会

分析: 暴力hash 代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n, m, a[25];
bool vis[N];

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int t; scanf("%d", &t);
    while(t--) {
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= m; ++i) scanf("%d", a + i);
        int ans = 0;
        memset(vis, false, sizeof vis);
        for(int i = 1; i <= m; ++i) {
            for(int j = a[i]; j <= n; j += a[i])
                if(!vis[j]) ++ans, vis[j] = true;
        }
        printf("%d\n", ans);
    }
    return 0;
}

B - 数论基础知识测试

代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;


int euler(int n) {
    int ret = n, t = n;
    for(int i = 2; i * i <= n; i++) {
        if(t % i == 0) {
            ret = ret / i * (i - 1);
            while(t % i == 0) t /= i;
        }
    }
    if(t > 1) ret = ret / t * (t - 1);
    return ret;
}

int exgcd(int a, int b, int &x, int& y) {
    int d = a;
    if(!b) x = 1, y = 0;
    else {
        d = exgcd(b, a % b, y, x);
        y -= (a / b) * x;
    }
    return d;
}

int inv(int a, int m) {
    int x, y;
    exgcd(a, m, x, y);
    return (m + x % m) % m;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    int op;
    while(scanf("%d", &op) == 1) {
        int ans;
        if(op == 1) {
            int n; scanf("%d", &n);
            for(int i = 1; i <= n; ++i) {
                int x; scanf("%d", &x);
                if(i == 1) ans = x;
                else ans = __gcd(ans, x);
            }
        } else if(op == 2) {
            int x, m; scanf("%d%d", &x, &m);
            ans = inv(x, m);
        } else {
            int x; scanf("%d", &x);
            ans = euler(x);
        }
        printf("%d\n", ans);
    }
    return 0;
}

C - 小Y喜欢拆拆拆

分析: 模拟 代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

int n;

bool isPrime(int x) {
    for(int i = 2; i * i <= x; ++i)
        if(x % i == 0) return false;
    return true;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%d", &n) == 1) {
        set<int> s;
        while(true) {
            if(s.count(n)) {
                n = -1;
                break;
            }
            s.insert(n);
            if(isPrime(n)) break;
            else {
                int t = n, sum = 0;
                for(int i = 2; i * i <= n; ++i) {
                    while(t % i == 0) {
                        sum += i;
                        t /= i;
                    }
                    if(t == 1) break;
                }
                if(t > 1) sum += t;
                n = sum;
            }
        }
        printf("%d\n", n);
    }
    return 0;
}

D - NT的数字

分析: 被8整除的特点后三位能被整除, 特判 长度 < 3 的全排列 然后暴力枚举1000以内能被8整除的数字 看给出的能不能构造 代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

char s[1005];
int n, have[10];

bool judge() {
    bool can = false;
    for(int i = 0; i < 1000; ++i) {
        if(i % 8) continue;
        int d = 0, t = i, cur[10] = {};
        while(t) {
            cur[t % 10]++;
            t /= 10;
            d++;
        }
        if(d == 0) { //000
            if(have[0] >= 3) can = true;
        } else {
            if(d == 1) cur[0] += 2;
            if(d == 2) cur[0] += 1;
            bool ok = true;
            for(int j = 0; j < 10; ++j)
                if(have[j] < cur[j]) ok = false;
            can = ok;
        }
        if(can) break;
    }
    return can;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    while(scanf("%s", s) == 1) {
        memset(have, 0, sizeof have);
        for(int i = 0; s[i]; ++i)
            have[s[i] - '0']++;

        n = strlen(s);
        if(n <= 3) {
            sort(s, s + n);
            bool ok = false;
            do {
                int x = atoi(s);
                if(x % 8 == 0) {
                    ok = true;
                    break;
                }
            } while(next_permutation(s, s + n));
            puts(ok ? "YES" : "NO");
            continue;
        }

        puts(judge() ? "YES" : "NO");
    }
    return 0;
}

E - NT的表白

题意: 求1111....1111%b = ? 分析1:  结论直接秒 b | a的前提下             

ACdream 简单数论 专题
ACdream 简单数论 专题

             111…111  % b= ((10^a - 1) / 9)  % b = (10^a -1) % (9*b) / 9              详情看:  点击打开链接                

ACdream 简单数论 专题
ACdream 简单数论 专题

            分析2: 我的思路 根据 a = x * y =>  a % m = (x % m * y % m) %m  然后折半分治 O(logn) 代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

typedef long long LL;

LL x, m;

LL ksm(LL x, LL n, LL m) {
    LL ret = 1;
    while(n) {
        if(n & 1) ret = ret * x % m;
        x = x * x % m;
        n >>= 1;
    }
    return ret;
}

LL dfs(LL n) {
    if(n <= 5) {
        LL x = 0;
        for(int i = 1; i <= n; ++i)
            x = (x * 10 + 1) % m;
        return x;
    }
    LL tmp = dfs(n >> 1), mul = n & 1 ? 10 : 1;
//  cout << "tmp: " << tmp << " mul: " << mul << " " << ksm(10, n >> 1, m) << endl;
    return (tmp * ksm(10, n >> 1, m) % m * mul % m + tmp * mul % m + mul / 10) % m;
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
//    ios_base::sync_with_stdio(0);

    while(scanf("%lld%lld", &x, &m) == 2) {
        printf("%lld\n", dfs(x));
    }
    return 0;
}

分析3: f[n] = f[n-1]*10 + 1 然后构造矩阵 矩阵快速幂 同样是O(logn) 思路来自学长 代码: 就不贴了 很好写

F - 这题占坑备用

分析: 直接构造所有的NT数  注意也许可能爆LL? 转double判断一下 然后sort直接找就好了 代码:

//
//  Created by TaoSama on 2015-09-24
//  Copyright (c) 2015 TaoSama. All rights reserved.
//
//#pragma comment(linker, "/STACK:1024000000,1024000000")
#include <algorithm>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <map>
#include <queue>
#include <string>
#include <set>
#include <vector>

using namespace std;
#define pr(x) cout << #x << " = " << x << "  "
#define prln(x) cout << #x << " = " << x << endl
const int N = 1e5 + 10, INF = 0x3f3f3f3f, MOD = 1e9 + 7;

typedef long long LL;

vector<LL> all;
LL l, r;

int getLen(LL x) {
    int ret = 0;
    for(; x; x /= 10) ++ret;
    return ret;
}

void dfs(LL x) {
    for(int i = 2; i < 20; ++i) {
        if(1.0 * x * i > 1e18) break;
        LL y = x * i;
        if(i == getLen(y)) {
            all.push_back(y);
            dfs(y);
        }
    }
}

void gao() {
    for(int i = 0; i < 10; ++i) {
        all.push_back(i);
        if(i >= 5) dfs(i);
    }
    sort(all.begin(), all.end());
//  for(auto v : all) printf("%lld ", v); puts("");
}

int main() {
#ifdef LOCAL
    freopen("in.txt", "r", stdin);
//  freopen("out.txt","w",stdout);
#endif
    ios_base::sync_with_stdio(0);

    gao();
    while(scanf("%lld%lld", &l, &r) == 2) {
        int ans = upper_bound(all.begin(), all.end(), r) -
                  lower_bound(all.begin(), all.end(), l);
        printf("%d\n", ans);
    }
    return 0;
}
数学 - 数论 套题 acdream 简单数论
上一篇: 哗啦啦族的01背包问题（折半枚举）
下一篇: ACdream 简单数据结构 专题

继续阅读