「BZOJ4173」数学
2020-01-15 09:26:59来源:博客园 阅读 ()
「BZOJ4173」数学
题面
已知
\[\large{S(n,m)=\{k_{1},k_{2},\cdots k_{i}\}}\]
且每个 \(k\) 满足
\[\large{n \%k+m\%k\geq k}\]
求
\[\large{\phi(n)\times \phi(m)\times\sum_{k\in S(n,m) }\phi(k)\%998244353}\]
Part 1
令
\[\large{n=a_{1} \times k +b_{1} ,m=a_{2} \times k +b_{2}}\]
所以有
\[\large{b_{1}+b_{2} \geq k}\]
\[\large{(a_{1} \times k +b_{1})+(a_{2} \times k +b_{2}) \geq (a_{1}+a_{2}+1)\times k}\]
所以
\[\large{n+m \geq (a_{1}+a_{2}+1)\times k}\]
两边同时除以 \(k\) 并向下取整得
\[\large{\lfloor \frac{n+m}{k} \rfloor \geq a_{1}+a_{2}+1}\]
因为
\[\large{a_{1}=\lfloor \frac{n}{k} \rfloor ,a_{2}=\lfloor \frac{m}{k} \rfloor}\]
所以
\[\large{\lfloor \frac{n+m}{k} \rfloor \geq \lfloor \frac{n}{k} \rfloor+\lfloor \frac{m}{k} \rfloor+1}\]
\[\large{\lfloor \frac{n+m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor - \lfloor \frac{m}{k} \rfloor\geq 1}\]
已知
\[\large{\lfloor\frac{x}{y}\rfloor=\frac{x}{y}-\{\frac{x}{y}\}}\]
所以式子可化为
\[\large{\frac{n+m}{k}-\{\frac{n+m}{k}\}-(\frac{n}{k}-\{\frac{n}{k}\}+\frac{m}{k}-\{\frac{m}{k}\})} \geq 1\]
化简得
\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}\geq 1\]
因为
\[\large{0\leq\{\frac{n}{k}\}},\{\frac{m}{k}\},\{\frac{n+m}{k}\}<1\]
所以
\[\large{1<\{\frac{n}{k}\}}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}<2\]
又因为
\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}\geq 1,\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}\in N^{+}\]
所以
\[\large{\{\frac{n}{k}\}+\{\frac{m}{k}\}-\{\frac{n+m}{k}\}}= 1\]
即
\[\large{\lfloor \frac{n+m}{k} \rfloor - \lfloor \frac{n}{k} \rfloor - \lfloor \frac{m}{k} \rfloor= 1}\]
Part2
先忽视要求式子的部分, 得
\[\large{\sum_{k\in S(n,m)}\phi(k)}\]
即
\[\large{\sum_{n \%k+m\%k\geq k }\phi(k)}\]
即
\[\large{\sum_{k=1}^{n+m}\phi(k)\times\lfloor \frac{n+m}{k} \rfloor}-\sum_{k=1}^{n}\phi(k)\times\lfloor \frac{n}{k} \rfloor-\sum_{k=1}^{m}\phi(k)\times\lfloor \frac{m}{k} \rfloor\]
因为
\[\large{n=\sum_{d|n}\phi(d)}\]
所以
\[\large{\sum_{i=1}^{n+m}i-\sum_{i=1}^{n}i-\sum_{i=1}^{m}i=\frac{(n+m)\times(n+m-1)}{2}-\frac{n\times(n-1)}{2}-\frac{m\times(m-1)}{2}-}\]
\[\large{=n\times m}\]
结论
\[\large{ans=\large{\phi(n)\times \phi(m)\times n\times m\%998244353}}\]
代码
#include <bits/stdc++.h>
using namespace std;
const int mod=998244353;
unsigned long long n,m;
unsigned long long phi(unsigned long long x)
{
unsigned long long ans=x;
for (unsigned long long i=2;i*i<=x;i++)
{
if (x%i==0)
{
ans-=ans/i;
while (x%i==0) x/=i;
}
}
if (x>1) ans-=ans/x;
return ans%mod;
}
int main()
{
cin>>n>>m;
cout<<(phi(n)%mod)*(phi(m)%mod)%mod*(n%mod)%mod*(m%mod)%mod;
return 0;
}
原文链接:https://www.cnblogs.com/666DHG/p/Solution_001.html
如有疑问请与原作者联系
标签:
版权申明:本站文章部分自网络,如有侵权,请联系:west999com@outlook.com
特别注意:本站所有转载文章言论不代表本站观点,本站所提供的摄影照片,插画,设计作品,如需使用,请与原作者联系,版权归原作者所有
上一篇:Big Event
下一篇:寒假集训第一天---并查集题解
- [题记-数学-面试题]约瑟夫环-leetcode 2020-03-30
- 离散数学交并补运算、差运算、异或运算的实现--biaobiao88 2019-11-01
- 你这一辈子要用到的C数学函数都在这 2019-01-16
- [算法]浅谈求n范围以内的质数(素数) 2018-11-28
- NOIP复习之1 数学数论 2018-09-18
IDC资讯: 主机资讯 注册资讯 托管资讯 vps资讯 网站建设
网站运营: 建站经验 策划盈利 搜索优化 网站推广 免费资源
网络编程: Asp.Net编程 Asp编程 Php编程 Xml编程 Access Mssql Mysql 其它
服务器技术: Web服务器 Ftp服务器 Mail服务器 Dns服务器 安全防护
软件技巧: 其它软件 Word Excel Powerpoint Ghost Vista QQ空间 QQ FlashGet 迅雷
网页制作: FrontPages Dreamweaver Javascript css photoshop fireworks Flash