Loj#6053. 简单的函数

题目描述

数据范围

题解

这是min25板子题。
首先，我们发现， f ( p 1 ) = p x o r 1 f(p^1)=p\ xor\ 1 f(p1)=p xor 1
由于p是质数$(p>2)$，那么我们可以得到： f ( p ) = p − 1 = p 1 − p 0 f(p)=p-1=p^1-p^0 f(p)=p−1=p1−p0
因此，我们可以把f表示成一个多项式了。
然后我们就直接上min25。
不会的戳这里
一个特殊情况就是$f(2)=3,f(1)=1$，而实际计算出来的东东是$f(2)=1,f(1)=0$所以加上一个3即可。

代码

#include 
#include 
#include 
#include 
using namespace std;
const long long mo=1000000007;
const int maxn=1000010;long long zs[maxn],n,m,d[maxn],sum[maxn],id,wz1,wz2,id1[maxn],id2[maxn],g0[maxn],g1[maxn],nex,now;
int tot;
bool bz[maxn];long long qsm(long long a,long long b)
{long long t=1;long long y=a;while (b>0){if ((b&1)==1) t=t*y%mo;y=y*y%mo;b/=2;}return t;
}void getg()
{for (int i=1;i<=zs[0];i++){for (int j=1;j<=tot;j++){if (zs[i]*zs[i]<=d[j]){id=d[j]/zs[i];if (id<=m) wz1=id1[id];else wz1=id2[n/id];id=zs[i]-1;if (id<=m) wz2=id1[id];else wz2=id2[n/id];g0[j]=(g0[j]-(g0[wz1]-(i-1))%mo+mo)%mo;g1[j]=(g1[j]-zs[i]%mo*((g1[wz1]-sum[i-1]+mo)%mo)%mo+mo)%mo;}else{break;}}}
}long long gets(long long a,int b)
{if (a==0 || zs[b]>a) return 0;
//	printf("%lld\n",a);long long id=a,wz1,wz2;if (id<=m) wz1=id1[id]; else wz1=id2[n/id];long long ss=0;ss=((g1[wz1]-g0[wz1])-(sum[b-1]-(b-1))%mo+mo)%mo;for (int i=b;i<=zs[0];i++){if (zs[i]*zs[i]<=a){long long mi=zs[i];for (int e=1;mi*zs[i]<=a;e++,mi=mi*zs[i]){ss=(ss+(zs[i]^e)*gets(a/mi,i+1)%mo+(zs[i]^(e+1))%mo)%mo;}}else break;}return ss;
}int main()
{
//	freopen("data.in","r",stdin);
//	freopen("data.out","w",stdout);for (int i=2;i<=100000;i++){if (!bz[i]){zs[0]++;zs[zs[0]]=i;for (int j=1;j<=100000/i;j++){bz[j*i]=true;}}}for (int i=1;i<=zs[0];i++){sum[i]=(sum[i-1]+zs[i])%mo;}scanf("%lld",&n);if (n==1){printf("1\n");return 0;}m=sqrt(n);for (long long i=1;i<=n;i=nex+1){if (i>100000){int j=0;}nex=n/(n/i);d[++tot]=n/i;now=n/i;g0[tot]=(now-1)%mo;g1[tot]=(((now+1)%mo)*(now%mo)%mo*qsm(2,mo-2)%mo-1+mo)%mo;if (d[tot]<=m) id1[n/i]=tot;else id2[n/(n/i)]=tot;}getg();long long ans=gets(n,1);printf("%lld\n",(ans+3)%mo);
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！