3

十四届蓝桥杯-互质数个数

 1 year ago
source link: http://blog.linrty.com/2022/10/09/%E5%8D%81%E5%9B%9B%E5%B1%8A%E8%93%9D%E6%A1%A5%E6%9D%AF-%E4%BA%92%E8%B4%A8%E6%95%B0%E4%B8%AA%E6%95%B0/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client

十四届蓝桥杯-互质数个数

阅读数：15次

2022-10-09

十四届蓝桥杯互质数的个数

题目描述：

image-20230410093306132

首先可以应该可以想到不互质的个数肯定比较少，而与它互质的个数肯定多，所以可以找不互质的数用总数减去它，看到高幂，直接快速幂模板先搞上（比赛的时候比较傻逼，太久没写模板了，写太快直接写错了）

假如xx与aa不互质，那么肯定就和abab不互质，那么在1−ab1−ab以内的所有xx的倍数都不互质

那么问题就变成了如何求出在1−ab1−ab内xx的倍数的个数，然后就可以演变成求x∗y<=abx∗y<=ab，yy的最大值，所以也就变成了abab整除xx

然后，就是找一些细节问题了，我们可以发现，如果这么减的话，会出现一种情况，

比如x1x1和abab不互质，并且x2x2和abab不互质，那么假设x1x2x1x2也在1−ab1−ab范围内，那么是不是就意味着x1x2x1x2会减两次，多减了，所以需要重新加回去

然后就是取模的问题了，可以看到我们的思路之中出现了除法取模的情况，所以关于逆元的基础知识自己补一补这里就不详说了，直接说结论(a/b)%MOD(a/b)%MOD = a∗Inv(b)%MODa∗Inv(b)%MOD其中Inv(b)=bMOD−2%MODInv(b)=bMOD−2%MOD

以上就是整体的思路，那么就可以开始编写代码了

import java.util.ArrayList;
import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        long a,b;
        long MOD = 998244353;
        Scanner sc = new Scanner(System.in);
        a = sc.nextLong();
        b = sc.nextLong();
        long up = a;
        long res = qpow(a,b,MOD);
        long cnt = res;
        ArrayList<Integer> list = new ArrayList<Integer>();
        for (int i = 2; i <= up; i++) {
            if (a%i == 0){ // 与res不互质
                // (res/i)%MOD = res * Inv(i)%MOD
                cnt = (cnt + MOD - (res * qpow(i, MOD -2, MOD) % MOD))%MOD;
                // 如果2与3都和它不互质，那么会出现都减了6的倍数，所以还需要加回去
                for (int j = 0; j < list.size(); j++) {
                    int xx = list.get(j);
                    long tmp = xx * i;
                    cnt = (cnt + (res * qpow(tmp, MOD -2, MOD) % MOD))%MOD;
                }
                list.add(i);
                up/=i;
            }
        }
        System.out.println(cnt);
    }
    public static long qpow(long a, long b, long p) {
        long ans = 1;
        while (b > 0) {
            if ((b & 1) == 1) {
                ans = ans * a % p;
            }
            a = a * a % p;
            b >>= 1;
        }
        return ans;
    }
}
// 2 5
// 16


// 12 7
// 11943936

// 1000000000 1000000000000000000
// 539268642


// 224036583 1000000000000000000  超大素数
// 696203968

如有错误，望各位指正

本文作者： linrty
本文链接： http://blog.linrty.com/2022/10/09/%E5%8D%81%E5%9B%9B%E5%B1%8A%E8%93%9D%E6%A1%A5%E6%9D%AF-%E4%BA%92%E8%B4%A8%E6%95%B0%E4%B8%AA%E6%95%B0/
版权声明： 本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可。转载请注明出处！

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK