[luogu4626][一道水题2]

题目链接

思路

这个首先想到质因数分解。然后发现只要对于每个质数将ans乘以这个质数在从1到n中出现过的最高指数次就行了。
这个\(10^8\)令人发指。一直tle,最后发现吸口氧才能过。。

代码

#include<cstdio>
#include<iostream>
#include<bitset>
#define fi(s) freopen(s,"r",stdin);
#define fo(s) freopen(s,"w",stdout);
using namespace std;
typedef long long ll;
const int N = 100000000 + 100,mod = 100000007;
bitset<N>vis;
int dis[N/15];
ll read() {
    ll x = 0,f = 1;char c = getchar();
    while(c < '0' || c > '9') {
        if(c == '-') f = -1;
        c = getchar();
    }
    while(c >= '0' && c <= '9') {
        x = x * 10 + c - '0';
        c = getchar();
    }
    return x * f;
}
int js;
int n;
ll work(int x) {
    ll ans = 1,k = n;
    k /= x;
    while(k) {
        k /= x;
        ans = ans * x % mod;
    }
    return ans;
}
int main() {
    n = read();
    for(int i = 2;i <= n;++i) {
        if(!vis[i]) dis[++js] = i;
        for(int j = 1;j <= js && dis[j] * i <= n;++j) {
            vis[dis[j] * i] = 1;
            if(i % dis[j] == 0) break;
        }
    }
    ll ans = 1;
    for(int i = 1;i <= js;++i)
        ans = ans * work(dis[i]) % mod;
    cout<<ans;
    return 0;
}

一言

都是老中医,少给我开偏方。

全部评论

相关推荐

不愿透露姓名的神秘牛友
07-07 14:00
点赞 评论 收藏
分享
点赞 评论 收藏
分享
06-12 17:46
门头沟学院 Java
运营你豪哥:来说重点: ​1.项目前置,时间倒序。​​ 2.​项目描述强化结果与量化效果(STAR原则里的R)。​​ ​3.个人技能精炼,明确掌握程度,突出核心。​​ ​4.增加强有力开头的个人总结部分。​​ 5.​优化教育背景(成绩排名)、合并奖项与活动。​​
听劝,我这个简历该怎么改...
点赞 评论 收藏
分享
评论
点赞
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务