【BZOJ-4173】数学 欧拉函数 + 关于余数的变换

时间：2021-04-20 17:48:44

4173: 数学

Time Limit: 10 Sec  Memory Limit: 256 MB
Submit: 306  Solved: 163
[Submit][Status][Discuss]

Description

【BZOJ-4173】数学 欧拉函数 + 关于余数的变换

Input

输入文件的第一行输入两个正整数 。

Output

如题

Sample Input

5 6

Sample Output

240

HINT

N,M<=10^15

Source

Solution

数论好题，开始无从下手，推导后感觉新姿势++

题目大意:求$\varphi(n)*\varphi(m)*\sum_{k\in S(n,m)}\varphi(k) mod p$其中$p=998244353$且$S(n,m)=\left \{n mod k+m mod k>=k\right \}$

首先把式子拆解一下,先看$S(n,m)=\left \{n mod k+m mod k>=k\right \}$:

不妨设$n=q_{1}*k+r_{1}$,$m=q_{2}*k+r_{2}$

那么很显然有:$n mod k=r_{1}$,$n / k=q_{1}$,$m mod k=r_{2}$,$m / k=q_{2}$

那么$S(n,m)=\left \{n mod k+m mod k>=k\right \}$就可以先化成$S(n,m)=\left \{r_{1}+r_{2}>=k\right \}$

那么根据上述,同样的有:$n+m=(q_{1}+q_{2})*k+(r_{1}+r_{2})$

很显然$(r_{1}+r_{2})/k<=1$,如果有$r_{1}+r_{2}>=k$,那么$(n+m) mod k=r_{1}+r_{2}-k$,且$(n+m)/k=q_{1}+q_{2}+1$

这样发现,开始的$S(n,m)=\left \{n mod k+m mod k>=k\right \}$就可以等价为$\frac{n+m}{k}-\frac{n}{k}-\frac{m}{k}=1$

所以$\sum_{k\in S(n,m)}\varphi(k)$就可以等价成$\frac{n+m}{k}\sum_{k=1}^{n+m}\varphi(k)-\frac{n}{k}\sum_{k=1}^{n}\varphi(k)-\frac{m}{k}\sum_{k=1}^{m}\varphi(k)$

根据有一个性质$n=\sum_{d|n}\varphi(d)$那么上述式子可以转化成:$\sum_{i=1}^{n+m}-\sum_{i=1}^{n}-\sum_{i=1}^{m}$

根据求和公式$\frac{n(n-1)}{2}$再变换为$\frac{(n+m)(n+m-1)}{2}-\frac{n(n-1)}{2}-\frac{m(m-1)}{2}$

化简一下发现$\frac{(n+m)(n+m-1)}{2}-\frac{n(n-1)}{2}-\frac{m(m-1)}{2}=n*m$

所以最后的答案为$ans=\varphi(n)*\varphi(m)*n*m$

那么用$\sqrt{n}$的时间复杂度求出$\varphi$即可

Code

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

using namespace std;

long long read()

{

    long long x=,f=; char ch=getchar();

    while (ch<'' || ch>'') {if (ch=='-') f=-; ch=getchar();}

    while (ch>='' && ch<='') {x=x*+ch-''; ch=getchar();}

    return x*f;

}

#define p 998244353

long long n,m;

long long phi(long long x)

{

    long long y=(long long)sqrt(n+0.5);

    long long re=x;

    for(long long i=; i<=y; i++)

        if(!(x%i))

        {

            re=re/i*(i-);

            while(!(x%i)) x/=i;

        }

    if(x>) re=re/x*(x-);

    return re;

}

int main()

{

    n=read(),m=read();

    long long ans;

    ans=((((phi(n)%p)*(phi(m)%p))%p*(m%p))%p*(n%p))%p;

    printf("%lld\n",ans);

    return ;

}

很早以前写的..博客搬家没搬进来...

相关文章