当前位置:网站首页>(Codeforce 757)E. Bash Plays with Functions(积性函数)
(Codeforce 757)E. Bash Plays with Functions(积性函数)
2022-08-01 04:47:00 【AC__dream】
题目:
样例输入:
5
0 30
1 25
3 65
2 5
4 48
样例输出:
8
5
25
4
630
题意:
我们先来分析r=0的情况,假如我们现在求f0(n),n=p1^a1*p2^a2*……*pm^am
那么f0(n)就等于2^m,这是显然的,因为我们假设p=p1^b1*p2^b2*……*pm^bm,那么对于任意的bi(1<=i<=m)都有bi=0或者bi=ai,要不然不会存在q使得p*q=n且gcd(p,q)=1,那么我们就不难发现其实f0(x)是一个积性函数。假设对于n=p*q,gcd(p,q)=1,则p和q的质因子分解中不会存在相同质因子,不妨假设p有i个质因子,q有j个质因子,那么p*q就会有i+j个质因子,那么f0(pq)=2^(i+j)=2^i*2^j=f0(p)*f0(q),所以f0(x)是一个积性函数。
下面我用归纳法来证明对于任意的r都有fr(x)是一个积性函数。
我们知道对于r=0的情况f0(n)的值只与n的质因子的种类有关,而与具体的质因子无关,而r不为0的情况是由r=0的情况得到的,所以r不为0的时候与具体的质因子也不会有关系。我们上面推导了对于任意的r都有fr(x)是一个积性函数,所以我们求fr(n)时只需要看n的质因子分解情况即可,那么问题就转变为求解fr(p^i),p是一个质数,根据公式我们可以发现fr(p^i)=,又因为与具体的质因子无关,通过上式我们可以发现只与质因子的次数有关,那么我们就可以令f[i][j]记录fi(p^j)的值 ,由于n是小于1e6的,所以质因子分解中最高次数不会超过20,这样通过O(r*20)就可以预处理出来所有的数。当r=0时,根据其定义我们可以知道f[0][1]=1,f[0][i]=2(i>1),预处理一下即可
剩下的就是对于每组询问记录一下质因子次数,直接利用积性函数性质求解了。
下面是代码:
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<vector>
#include<cmath>
using namespace std;
const int N=1e6+10,mod=1e9+7;
long long f[N][21];//f[i][j]表示fi(p^j)
int prime[N],tt;
bool vis[N];
void init()
{
f[0][0]=1;
for(int i=1;i<=20;i++) f[0][i]=2;
for(int i=1;i<=1000000;i++)
{
long long ans=0;
for(int j=0;j<=20;j++)
{
ans=(ans+f[i-1][j])%mod;
f[i][j]=ans;
}
}
}
int main()
{
init();
int T;
cin>>T;
while(T--)
{
int r,n;
scanf("%d%d",&r,&n);
long long ans=1;
for(int i=2;i*i<=n;i++)
{
int cnt=0;
if(n%i==0)
{
while(n%i==0)
{
n/=i;
cnt++;
}
ans=ans*f[r][cnt]%mod;
}
}
if(n>1) ans=ans*f[r][1]%mod;
printf("%lld\n",ans);
}
return 0;
}
边栏推荐
- 56:第五章:开发admin管理服务:9:开发【文件上传到,MongoDB的GridFS中,接口】;(把文件上传到GridFS的SOP)
- typescript26 - literal types
- 怀念故乡的面条
- [FPGA tutorial case 43] Image case 3 - image sobel edge extraction through verilog, auxiliary verification through MATLAB
- Pyspark Machine Learning: Vectors and Common Operations
- 报错:AttributeError: module ‘matplotlib’ has no attribute ‘figure’
- typescript25 - type assertion
- typescript24-类型推论
- typescript21-接口和类型别名的对比
- Excel做题记录——整数规划优化模型
猜你喜欢
The method of solving stored procedure table name passing through variable in mysql
[kali-information collection] enumeration - DNS enumeration: DNSenum, fierce
Dry goods!How to Construct SRv6-TE Performance Test Environment Using Instrumentation
Interview Blitz 69: Is TCP Reliable?Why?
typescript26 - literal types
typescript24-类型推论
【kali-信息收集】枚举——DNS枚举:DNSenum、fierce
MySQL3
The difference between scheduleWithFixedDelay and scheduleAtFixedRate
C# | 使用Json序列化对象时忽略只读的属性
随机推荐
MySQL3
MySQL4
Excel做题记录——整数规划优化模型
请问shake数据库中想把源的db0的数据同步到目的db5,参数怎么设置呢?
Typescript22 - interface inheritance
Advice given by experts with four years of development experience in Flutter tutorial
Risk strategy important steps of tuning method
MySQL-数据定义语言-DDLdatebase define language
【云原生之kubernetes实战】kubernetes集群的检测工具——popeye
ModuleNotFoundError: No module named ‘tensorflow.keras‘报错信息的解决方法
TypeScript simplifies running ts-node
Interview Blitz 69: Is TCP Reliable?Why?
Message queue MySQL table for storing message data
7月编程排行榜来啦!这次有何新变化?
[FPGA tutorial case 43] Image case 3 - image sobel edge extraction through verilog, auxiliary verification through MATLAB
MySQL3
动态规划 01背包
博客系统(完整版)
项目风险管理必备内容总结
"ArchSummit: The cry of the times, technical people can hear"