当前位置: 首页 > news >正文

【2023ICPC网络赛I 】E. Magical Pair

在这里插入图片描述

当时在做洛谷U389682 最大公约数合并的时候我就想到把每个质因子分解出来然后跑高维前缀和,但是那一道题不是用这个方法,所有我也一直在思考这种做法是不是真的有用。因为昨天通过2024上海大学生程序设计竞赛I-六元组计数这道题我了解到了不少关于原根的性质,所以想着回来做去年网络赛的题目。因为我当时完全不了解原根,因此做不了这个题目,更看不懂题解,但是我现在已经大概掌握原根的知识,所以感觉做这道题还算比较轻松,而且这道题里面刚好就用到了曾经想到的质因数分解+高维前缀和,感觉十分有趣,于是写博客记录。

因为原根的题目一般都喜欢把0先处理掉,然后在处理不为0的情况。
很显然,如果想让左右两边为0,只需要满足 n ∣ x , n ∣ y n|x,n|y nx,ny,方案数为 ( n − 1 ) 2 (n-1)^2 (n1)2

然后我的想法是先列出一个 ( n − 1 ) ∗ ( n − 1 ) (n-1)*(n-1) (n1)(n1)的表, 1 < = x < = n − 1 , 1 < = y < = n − 1 , a i , j = i j 1<=x<=n-1,1<=y<=n-1,a_{i,j}=i^j 1<=x<=n1,1<=y<=n1,ai,j=ij。实际上,表上每一个位置都表示 n ∗ ( n − 1 ) n*(n-1) n(n1)个数,因为实际上它的行坐标可以加上若干个 n n n,列坐标可以加上若干个 n − 1 n-1 n1。然后就可以发现任意两个值相同的位置(可以一样)都恰好对应了一个解(我也不清楚如果以前没有看过题解能不能想到这一步)。比如两个坐标分别为 ( x 1 , y 1 ) , ( x 2 , y 2 ) (x_1,y_1),(x_2,y_2) (x1,y1),(x2,y2),如果我们想形成一个解,那么就必须要让 x 1 + k 1 n = y 2 + k 2 ( n − 1 ) , y 1 + k 3 ( n − 1 ) = x 2 + k 4 n x_1+k_1n=y_2+k_2(n-1),y_1+k_3(n-1)=x_2+k_4n x1+k1n=y2+k2(n1),y1+k3(n1)=x2+k4n,这个根据扩展欧几里得可以知道如果想找到另外一个解,那么 k 1 , k 4 k_1,k_4 k1,k4都必须改变 n − 1 n-1 n1 k 2 , k 3 k_2,k_3 k2,k3都必须改变 n n n,因此两个相同值的位置恰好对应一个解。

因此,我们就必须算出每个数出现的次数,答案就是这个出现次数的平方和。

根据原根的性质,和 n − 1 n-1 n1最大公因数相同的数出现次数一样, 然后我们就把和 n − 1 n-1 n1最大公因数相同的数全部在一个组,然后考虑组合组之间的影响(详见2024上海大学生程序设计竞赛I-六元组计数&原根知识详解。

我们就考虑每个集合的最小的数,那么只有它的因子所在的集合会出现这个数,实际上就是一个周期出现一次, g c d ( x , n − 1 ) = y gcd(x,n-1)=y gcd(x,n1)=y的数有 y y y个周期,所以贡献就是。

( n − 1 ) 2 + ∑ i ∣ n − 1 ϕ ( n − 1 i ) ( ∑ j ∣ i ϕ ( n − 1 j ) j ) 2 (n-1)^2+\sum_{i|n-1}\phi(\frac{n-1}{i})(\sum_{j|i}\phi(\frac{n-1}{j})j)^2 (n1)2+in1ϕ(in1)(jiϕ(jn1)j)2

我们可以预处理出 2 ∗ 1 0 7 2*10^7 2107以内的质数(实测表明n-1的所有素因子都不会超过4*10^14,所有我只用处理出这么多),然后分解完质因数就用高位前缀和把 ∑ j ∣ i ϕ ( n − 1 j ) j \sum_{j|i}\phi(\frac{n-1}{j})j jiϕ(jn1)j计算出来即可。

#include<bits/stdc++.h>
#define rep(i,x,y) for(int i=x;i<=y;i++)
#define dwn(i,x,y) for(int i=x;i>=y;i--)
#define ll long long
using namespace std;
template<typename T>inline void qr(T &x){x=0;int f=0;char s=getchar();while(!isdigit(s))f|=s=='-',s=getchar();while(isdigit(s))x=x*10+s-48,s=getchar();x=f?-x:x;
}
int cc=0,buf[31];
template<typename T>inline void qw(T x){if(x<0)putchar('-'),x=-x;do{buf[++cc]=int(x%10);x/=10;}while(x);while(cc)putchar(buf[cc--]+'0');
}
const int N=2e7+10,M=2e5+10,mod=998244353;
int cnt;ll p[N];bool v[N];
ll n,ans;
struct node{ll x,y;
}a[210];int m;ll val[210];
ll phi[M],lim,dp[M],num[M];
void solve(){qr(n);if(n==2){puts("2");return;}n--;ll nn=n;ans=(n%mod)*(n%mod)%mod;m=0;rep(i,1,cnt){if(p[i]*p[i]>n)break;if(n%p[i]==0){a[++m].x=p[i];a[m].y=0;while(n%p[i]==0)a[m].y++,n/=p[i];}}if(n>1)a[++m]=(node){n,1};val[1]=1;rep(i,2,m)val[i]=val[i-1]*(a[i-1].y+1);lim=val[m]*(a[m].y+1);rep(i,0,lim-1){if(!i){phi[i]=1;num[i]=1;continue;}bool bk=0;rep(j,1,m){ll t=i/val[j]%(a[j].y+1);if(t){if(t==1)phi[i]=phi[i-val[j]]*(a[j].x-1);else phi[i]=phi[i-val[j]]*a[j].x;num[i]=num[i-val[j]]*a[j].x;break;}}}rep(i,0,lim-1)dp[i]=(phi[lim-1-i]%mod)*(num[i]%mod)%mod;rep(i,1,m)rep(j,val[i],lim-1)if(j/val[i]%(a[i].y+1))(dp[j]+=dp[j-val[i]])%=mod;rep(i,0,lim-1){dp[i]=dp[i]*dp[i]%mod;(ans+=(phi[lim-1-i]%mod)*dp[i]%mod)%=mod;}cout<<ans<<endl;
}
int main(){rep(i,2,20000000){if(!v[i])v[i]=1,p[++cnt]=i;for(int j=1;j<=cnt&&i*p[j]<=20000000ll;j++){v[i*p[j]]=1;if(i%p[j]==0)break;}}int tt;qr(tt);while(tt--)solve();return 0;
}
http://www.lryc.cn/news/391879.html

相关文章:

  • Kafka-服务端-网络层-源码流程
  • 百日筑基第十一天-看看SpringBoot
  • Generative Modeling by Estimating Gradients of the Data Distribution
  • vector与list的简单介绍
  • 四种线程池的使用,优缺点分析
  • 什么是 BEM 规范
  • 【Node.JS】入门
  • Amazon SageMaker 机器学习之旅的助推器
  • TransMIL:基于Transformer的多实例学习
  • 3.用户程序与驱动交互
  • 尽量不写一行if...elseif...写出高质量可持续迭代的项目代码
  • xcrun: error: unable to find utility “simctl“, not a developer tool or in PATH
  • 【linux高级IO(一)】理解五种IO模型
  • 前端引用vue/element/echarts资源等引用方法Blob下载HTML
  • 昇思MindSpore学习笔记2-01 LLM原理和实践 --基于 MindSpore 实现 BERT 对话情绪识别
  • uniapp实现图片懒加载 封装组件
  • 持续交付:自动化测试与发布流程的变革
  • VBA常用的字符串内置函数
  • 大数据面试题之Spark(7)
  • AI绘画 Stable Diffusion图像的脸部细节控制——采样器全解析
  • liunx离线安装Firefox
  • UNet进行病理图像分割
  • 初二数学基础差从哪开始补?附深度解析!
  • 【C语言】return 关键字
  • 华为机试HJ13句子逆序
  • 代码随想录day40 动态规划(5)
  • FFmpeg 命令行 音视频格式转换
  • Jmeter使用JSON Extractor提取多个变量
  • c++ 设计模式 的课本范例(下)
  • 结合数据索引结构看SQL的真实执行过程