AcWing
  • 首页
  • 课程
  • 题库
  • 更多
    • 竞赛
    • 题解
    • 分享
    • 问答
    • 应用
    • 校园
  • 关闭
    历史记录
    清除记录
    猜你想搜
    AcWing热点
  • App
  • 登录/注册

牛客网2019年6月模拟校招一题

作者: 作者的头像   Hilbert-v ,  2019-06-21 13:01:50 ,  所有人可见 ,  阅读 1125


2


题目描述:牛牛跟毛毛在玩一个有趣的猜数游戏,由牛牛给出条件,毛毛猜,条件只有Y/N两种,第n个条件为这个数是否是n的倍数(如YYN表示这个数是1的倍数,是2的倍数,不是3的倍数)。但是牛牛也有给错条件的时候,比如NYY(这表示这个数不是1的倍数,是2和3的倍数,但是这显然是错误的)。现在给定n,求所有合法序列的条件数。
样例:输入5
输出12

text:

#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cstdio>
using namespace std;
const int N = 210, mod = 1000000000;

int main() {
    int n;

    long long ans = 1;

    bool vis[N];
    scanf("%d", &n);

    for (int i = 2; i <= n; i++) {
        if (vis[i]) continue;
        for (int j = i; j <= n; j += i)
            vis[j] = true;

        int cnt = 1;
        for (int j = i; j <= n; j *= i)
            cnt++;

        ans = ans * cnt % mod;
    }

    cout << ans << endl;

    return 0;
}

这是来自WZC1995老哥的解答,利用质数的想法。鄙人学艺不精,还在研究中。

2 评论


用户头像
wzc1995   2019-06-22 00:43         踩      回复

棒!

用户头像
wzc1995   2019-06-22 02:31         踩      回复

个人想法是,每个数字都可以拆成互质的若干个数字相乘,这样如果质数和质数幂次的数字的Y/N确定了后,其他所有的数字就都确定了。比如 n = 5,小于等于 5 的质数及其幂次有 (2, 4)、(3)、(5),每一组合法情况的个数相乘就是答案。比如 (2, 4) 合法情况只有 3 种, (3) 和 (5) 分别有 2 种,所以答案是 3 * 2 * 2 = 12。


App 内打开
你确定删除吗?
1024
x

© 2018-2025 AcWing 版权所有  |  京ICP备2021015969号-2
用户协议  |  隐私政策  |  常见问题  |  联系我们
AcWing
请输入登录信息
更多登录方式: 微信图标 qq图标 qq图标
请输入绑定的邮箱地址
请输入注册信息