【欧拉函数】BZOJ4173-数学
2024-10-12 01:57:05
【题目大意】
【思路】
基本是popoqqq大爷的题解,稍微添加了几句自己的注释,方便理解
同理,如果n%k+m%k<k等价于0
=∑([(n+m)/k]-[n/k]-[m/k])×φ(k) ……因为k不满足条件的时候前面为0
……其实右边两个∑也是k=1..(m+n),但是k>n的时候,[n/k]显然为0,m同理。
【错误点XXXXD】
……程序烧杯,po也是烧杯。不要忘了ll,不要忘了MOD……
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define MOD 998244353
using namespace std;
typedef long long ll; ll phi(ll x)
{
ll ret=x;
for (ll i=;i*i<=x;i++)
{
if (x%i==)
{
ret-=ret/i;
while (x%i==) x/=i;
}
}
if (x>) ret-=ret/x;
return ret%MOD;
} void solve()
{
ll n,m;
scanf("%lld%lld",&n,&m);
printf("%lld",(phi(n)%MOD)*(phi(m)%MOD)%MOD*(n%MOD)%MOD*(m%MOD)%MOD);
} int main()
{
solve();
return ;
}
最新文章
- 第一章 数据库概述、MySQL的安装和配置
- 北邮oj 题
- CentOS6.6搭建LNMP环境
- javascript模块化应用
- 设计4个线程,其中两个线程每次对j增加1,另外两个线程对j每次减少1
- Java正则表达式的最简单应用
- 【转】设计模式(三)建造者模式Builder(创建型)
- 团队博客——Sprint计划会议1
- OC - 13.数据解析(JSON与XML)
- 【JAVA零基础入门系列】Day4 变量与常量
- Javascript数组系列一之栈与队列
- 原生js作用域(红宝书)
- poj1177 矩形周长并
- DNS的域名的解析解决办法(openDNS)
- P1948 [USACO08JAN]电话线Telephone Lines(二分答案+最短路)
- Gravitee.io api gateway 试用
- Docker容器 暴露多个端口
- 记一次 oracle 12.2 RAC : Transaction recovery: lock conflict caught and ignored
- 20155227 《Java程序设计》实验五 Java网络编程及安全实验报告
- R dataframe 遗忘, which 矩阵搜索