acwing 4968 互质数的个数 | vegeone

vegeone
0%

acwing 4968 互质数的个数

发表于 分类于 Valine：

题意

给定，求与范围内与互质的数的个数

思路

​ 这个就是欧拉函数的定义。

首先根据唯一分解定理可得：设，其中为质数，有$\phi(n)=n\prod_{i=1}^s\frac{p_i-1}{p_i}，其中后面连乘的部分与k_i无关，那么可以直接由a来获取所有p_i，直接分解质因数即可。对于n，根据同余，可以通过快速幂得到。答案要求对大质数取余，除某个数等于乘该数的余数减二次方，即\frac{a}{b} \% mod = ab^{mod-2}$就是逆元。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<bits/stdc++.h>
using namespace std;
#define endl '\n'
typedef unsigned long long ull;
const ull mod=998244353;
typedef pair<int,int>pp;
ull qmi(ull a,ull b){
    ull res=1;
    while(b){
        if(b&1)res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
void solve()
{
    ull a,b;
    cin>>a>>b;

    if(a==1){
        cout<<0<<endl;
        return;
    }
    if(a==mod&&b==1){
        cout<<mod-1<<endl;
        return;
    }
    ull res=qmi(a,b);
    ull temp=a;
    for(int i=2;i*i<=temp;++i){
        if(temp%i==0)res=1ll*res*(i-1)%mod*qmi(i,mod-2)%mod;
        while(temp%i==0)temp/=i;
    }
    if(temp!=1)res=1ll*res*(temp-1)%mod*qmi(temp,mod-2)%mod;
    cout<<res<<endl;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    int T=1;
    // cin>>T;
    while(T--)	solve();
    return 0;
}