专栏首页数据结构与算法Hackerrank GCD Product(莫比乌斯反演)

Hackerrank GCD Product(莫比乌斯反演)

题意

题目链接

Sol

一道咕咕咕了好长时间的题

题解可以看这里

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = 1e7 + 5e6 + 10,  mod = 1e9 + 7, mod2 = 1e9 + 6;
int N, M, vis[MAXN], prime[MAXN], mu[MAXN], f[MAXN], tot;
int add(int x, int y) {
    if(x + y < 0) return x + y + mod;
    return x + y >= mod ? x + y - mod : x + y;
}
int mul(int x, int y) {
    return 1ll * x * y % mod;
}
int fp(int a, int p) {
    int base = 1;
    while(p) {
        if(p & 1) base = mul(base, a);
        a = mul(a, a); p >>= 1;
    }
    return base;
}
void sieve(int N) {
    vis[1] = 1; mu[1] = 1;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, mu[i] = -1;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {mu[i * prime[j]] = 0; break;}
            else mu[i * prime[j]] = -mu[i];
        }
    }
    for(int i = 1; i <= tot; i++) 
        for(LL j = prime[i]; j <= N; j *= prime[i])
            f[j] =prime[i];
    for(int i = 1; i <= N; i++) if(!f[i]) f[i] = 1;
}
signed main() {
    cin >> N >> M;
    sieve(1e7 + 5e6);
    //for(int i = 1; i <= 100; i++) printf("%d %d\n", i, f[i]);
    int ans = 1;
    for(int i = 1; i <= N; i++) {
        if(f[i] == 1) continue;
        ans = mul(ans, fp(f[i], 1ll * (N / i) * (M / i) % mod2));
    }
    cout << ans;
    return 0;
}
/*
100000 50000 200 300
100 2 1 1
*/

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • BZOJ2655: calc(dp 拉格朗日插值)

    设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数

    attack
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack
  • AIM Tech Round 5 B. Unnatural Conditions(思维)

    题目链接:http://codeforces.com/contest/1028/problem/B

    Ch_Zaqdt
  • PAT 1004 Counting Leaves

    1004. Counting Leaves (30) 时间限制 400 ms 内存限制 65536 kB 代码长度限制 16000 B ...

    ShenduCC
  • BZOJ2655: calc(dp 拉格朗日插值)

    设\(f[i][j]\)表示选了\(i\)个严格递增的数最大的数为\(j\)的方案数

    attack
  • 洛谷P4424 [HNOI/AHOI2018]寻宝游戏(思维题)

    那么我们把每一列上的数和他之前的操作符分别拿出来看成一些序列,显然这个序列要满足最后一个\(\mid 1\)要在\(\& 0\)之后

    attack
  • 【USACO 2.1】The Castle

    饶文津
  • 1466: [蓝桥杯2019初赛]等差数列

    数学老师给小明出了一道等差数列求和的题目。但是粗心的小明忘记了一部分的数列,只记得其中N 个整数。现在给出这N 个整数,小明想知道包含这N 个整数的最短的等差数...

    可爱见见
  • 洛谷2017 5月月赛R1

    我只想说面对这种难度的题目就是冲着20%的数据暴力。。。 分数:40+20+36.1+38+0+19 T1 签到题 III 题目背景 pj组选手zzq近日学会了...

    attack

扫码关注云+社区

领取腾讯云代金券