BZOJ 4652 [Noi2016]循环之美
发布日期:2021-05-04 16:55:24 浏览次数:26 分类:技术文章

本文共 2879 字,大约阅读时间需要 9 分钟。

题目链接

题解

容易发现,若 i j \frac{i}{j} ji k k k进制下为纯循环小数,那么必定有

i k l = i m o d    j k l = 1 m o d    j ik^l=i\mod{j}\\ k^l=1\mod{j} ikl=imodjkl=1modj
因此 gcd ⁡ ( j , k ) = 1 \gcd(j,k)=1 gcd(j,k)=1

那么题目要求的就是

F ( n , m , k ) = ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = 1 ] [ gcd ⁡ ( j , k ) = 1 ] F(n,m,k)=\sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j)=1][\gcd(j,k)=1] F(n,m,k)=i=1nj=1m[gcd(i,j)=1][gcd(j,k)=1]
反演得到
F ( n , m , k ) = ∑ d ∣ k F ( m d , n , d ) F(n,m,k)=\sum_{d|k}F(\frac{m}{d},n,d) F(n,m,k)=dkF(dm,n,d)
边界条件
F ( 0 , m , k ) = F ( n , 0 , k ) = 0 F ( n , m , 1 ) = ∑ i = 1 min ⁡ ( n , m ) μ ( i ) ⌊ n i ⌋ ⌊ m i ⌋ F(0,m,k)=F(n,0,k)=0\\ F(n,m,1)=\sum_{i=1}^{\min(n,m)}\mu(i)\lfloor\frac{n}{i}\rfloor\lfloor\frac{m}{i}\rfloor F(0,m,k)=F(n,0,k)=0F(n,m,1)=i=1min(n,m)μ(i)inim
注意需要记忆化。

代码

#include #include 
#include
int read(){
int x=0,f=1; char ch=getchar(); while((ch<'0')||(ch>'9')) {
if(ch=='-') {
f=-f; } ch=getchar(); } while((ch>='0')&&(ch<='9')) {
x=x*10+ch-'0'; ch=getchar(); } return x*f;}const int maxk=2000;const int maxn=1000000;int p[maxn+10],prime[maxn+10],cnt,mu[maxn+10],sum[maxn+10],d[maxk+10][maxk+10];int getprime(){
p[1]=mu[1]=1; for(int i=2; i<=maxn; ++i) {
if(!p[i]) {
prime[++cnt]=i; mu[i]=-1; } for(int j=1; (j<=cnt)&&(i*prime[j]<=maxn); ++j) {
int x=i*prime[j]; p[x]=1; if(i%prime[j]==0) {
mu[x]=0; break; } mu[x]=-mu[i]; } } for(int i=1; i<=maxn; ++i) {
sum[i]=sum[i-1]+mu[i]; } for(int i=1; i<=maxk; ++i) {
if(mu[i]) {
for(int j=i; j<=maxk; j+=i) {
d[j][++d[j][0]]=i; } } } return 0;}std::map
mp;int getsum(int n){
if(n<=maxn) {
return sum[n]; } if(mp.count(n)) {
return mp[n]; } int ans=1; for(int l=2,r; l<=n; l=r+1) {
r=n/(n/l); ans-=(r-l+1)*getsum(n/l); } return mp[n]=ans;}struct data{
int n,m,k; data(int _n=0,int _m=0,int _k=0):n(_n),m(_m),k(_k){
} bool operator <(const data &oth) const {
return (n==oth.n)?((m==oth.m)?(k
mf;long long F(int n,int m,int k){ if((n==0)||(m==0)) { return 0; } data da(n,m,k); if(mf.count(da)) { return mf[da]; } long long res=0; if(k==1) { for(int l=1,r,s,t=0; l<=std::min(n,m); l=r+1,t=s) { r=std::min(n/(n/l),m/(m/l)); s=getsum(r); res+=1ll*(s-t)*(n/l)*(m/l); } mf[data(m,n,k)]=res; } else { for(int i=1; (i<=d[k][0])&&(d[k][i]<=m); ++i) { res+=mu[d[k][i]]*F(m/d[k][i],n,d[k][i]); } } return mf[da]=res;}int n,m,k;int main(){ getprime(); n=read(); m=read(); k=read(); printf("%lld\n",F(n,m,k)); return 0;}

转载地址:https://blog.csdn.net/wang3312362136/article/details/86176834 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:BZOJ 3512 DZY Loves Math IV
下一篇:BZOJ 4913 [Sdoi2017] 遗忘的集合

发表评论

最新留言

哈哈,博客排版真的漂亮呢~
[***.90.31.176]2024年03月25日 20时03分40秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

用matlab写出信源熵,计算离散信源的熵matlab实现 2019-04-21
php表单yii2,Yii2创建表单(ActiveForm)方法详解 2019-04-21
php 程序授权机制,授权认证详细说明 2019-04-21
java 命令提示符,如何使用Java打开命令提示符并插入命令? 2019-04-21
IP/tzgm.php,LianjiaSpider/在售数量.ipynb at master · BerSerK/LianjiaSpider · GitHub 2019-04-21
linux移动文件的脚本,使用Linux脚本移动文件 2019-04-21
linux查看系统所有变量,Linux系统各指标命令 2019-04-21
linux打印机守护程序,linux下怎么编写守护程序呢? 2019-04-21
嵌入式linux 设置时间,time_clock控件应用,使用命令date -s 12:00:00手动设置时间后,时间就停住不走了,我在Ubuntu和嵌入式Linux平台都测试到了... 2019-04-21
linux 8086下编译,Ubuntu18.04/Linux下安装DosBox进行8086汇编 2019-04-21
linux监控windows,zabbix监控之linux及windows客户端安装配置 2019-04-21
linux中怎么卸载tree,Liunx系统命令中tree命令详解 2019-04-21
linux 网络音箱 混音6,Linux音频编程(三)混音器介绍 2019-04-21
node与mysql开源_node与mysql的相互使用————node+mysql 2019-04-21
python合并列表重新排序_python – 将两个已排序的列表合并为一个更大的排序列表... 2019-04-21
vbs用mysql语句查询数据库_vbs脚本实现window环境下的mysql数据库的备份及删除早期备份... 2019-04-21
mysql连接nginx_nginx四层负载均衡连接mysql 2019-04-21
mysql截取栏目字符_substring从指定字符串开始截取(图) 2019-04-21
python 函数参数前面两个星号_Python中参数前面一个星号两个星号(*参数,**参数)起什么作用呢?... 2019-04-21
python类属性初始化_Python类定义、属性、初始化和析构 2019-04-21