BZOJ 4173 数学

Description

ff.jpg

Input

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

Output

如题

Sample Input

5 6

Sample Output

240

HINT

N,M<=10^15

题解

简单来说就是找规律

答案为a*b*phi(a)*phi(b)

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
const long long MOD = 998244353;
long long phi(long long x)
{
    double ans = x;
    int i = 2;
    int Sqrt = ceil(sqrt(x));
    while (x != 1)
    {
        if (i > Sqrt)
        {
            ans *= (1 - (double)1 / x);
            break;
        }
        if (x % i == 0)
        {
            ans *= (1 - (double)1 / i);
            while (x % i == 0)
                x /= i;
        }
        i++;
    }
    return (long long)ans;
}
int main()
{
    long long a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld",((((a%MOD)*(b%MOD)%MOD)*(phi(a)%MOD)%MOD)*(phi(b)%MOD))%MOD);
    //while(1);
}

本文作者 : NekoMio
知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议进行许可。
本文链接 : https://www.nekomio.com/2017/08/12/92/
上一篇
下一篇