【BZOJ4173】数学

4173: 数学

Time Limit: 10 Sec Memory Limit: 256 MB
Submit: 528 Solved: 258
[Submit][Status][Discuss]

Description

Input

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

Output

如题

Sample Input

5 6

Sample Output

240

HINT

N,M<=10^15

sol：推公式

$m mod k + n mod k ge k$

$= n- k* lfloor frac{n}{k} floor + m - k* lfloor frac{m}{k} floor ge k$

$=lfloor frac{(n+m)}{k} floor - lfloor frac{n}{k} floor - lfloor frac{m}{k} floor = 1$

然后上述式子合并一下然后类似反演的推一下就好了我真是懒得写了QAQ

中途需要硬拆数列前缀和

UPD:

哇我这篇排名居然这么高我就再写一点吧

考虑容斥那么$sum_{lfloor frac{(n+m)}{k} floor - lfloor frac{n}{k} floor - lfloor frac{m}{k} floor = 1} phi(k)$

$=sum_{k=1}^{n+m}phi(k)*lfloor frac{(n+m)}{k} floor - sum_{k=1}^{n}phi(k) * lfloor frac{n}{k} floor - sum_{k=1}^{m}phi(k)*lfloor frac{m}{k} floor$

根据数论知识我们有$n=sum_{d|n}phi(d)$

于是简化式子 $sum_{i=1}^{n+m}i-sum_{i=1}^{n}i-sum_{i=1}^{m}i$

等差数列求和得到该式为$n*m$（不信自己证明）

至于为啥$n- k* lfloor frac{n}{k} floor + m - k* lfloor frac{m}{k} floor ge k=lfloor frac{(n+m)}{k} floor - lfloor frac{n}{k} floor - lfloor frac{m}{k} floor = 1$ 消k我还真没搞懂看到某个大爷说显然只有两种取值不是很懂……？

然后答案就是$phi(n)*phi(m)*n*m$复杂度$O(sqrt{n}*logn)$

/*To The End Of The Galaxy*/
#include<cstdio>
#include<cstdlib>
#include<iostream>
#include<cstring>
#include<algorithm>
#include<queue>
#include<iomanip>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<complex>
#define debug(x) cerr<<#x<<"="<<x<<endl
#define INF 0x7f7f7f7f
#define llINF 0x7fffffffffffll
using namespace std;
typedef pair<int,int> pii;
typedef long long ll;
inline int init()
{
    int now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
inline long long llinit()
{
    long long now=0,ju=1;char c;bool flag=false;
    while(1)
    {
        c=getchar();
        if(c=='-')ju=-1;
        else if(c>='0'&&c<='9')
        {
            now=now*10+c-'0';
            flag=true;
        }
        else if(flag)return now*ju;
    }
}
ll ans,mod;
ll getphi(ll x)
{
    ll ret=x,tmp=x;
    for(ll i=2;(ll)i*i<=tmp;i++)
    {
        if(x%i==0)
        {
            ret/=i;ret*=(i-1);
            while(x%i==0)
            {
                x/=i;
            }
        }
        if(x==1)break;
    }
    if(x>1)ret/=x,ret*=(x-1);
    return ret%mod;
}
#ifdef unix
    #define LLD "%lld"
#else
    #define LLD "%I64d"
#endif
int main()
{    
    ll n,m;mod=998244353LL;
    n=llinit();m=llinit();
    ans=(((((n%mod)*(m%mod))%mod)*getphi(n)%mod)*getphi(m)%mod)%mod;
    printf(LLD,ans);
    return 0;
}

View Code