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

4173: 数学

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

Description

Input

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

Output

如题

Sample Input

5 6

Sample Output

240

HINT

N,M<=10^15

Source

Solution

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

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

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

不妨设$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 ight }$就可以先化成$S(n,m)=left {r_{1}+r_{2}>=k ight }$

那么根据上述,同样的有:$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 ight }$就可以等价为$frac{n+m}{k}-frac{n}{k}-frac{m}{k}=1$

所以$sum_{kin 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=0,f=1; char ch=getchar();
    while (ch<'0' || ch>'9') {if (ch=='-') f=-1; ch=getchar();}
    while (ch>='0' && ch<='9') {x=x*10+ch-'0'; 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=2; i<=y; i++)
        if(!(x%i))
        {
            re=re/i*(i-1);
            while(!(x%i)) x/=i;
        }
    if(x>1) re=re/x*(x-1);
    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
",ans);   
    return 0;
}

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