前缀lcm 50pts求助,WA了后面五个点
查看原帖
前缀lcm 50pts求助,WA了后面五个点
585805
MCRS_lizi楼主2022/8/25 11:22
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int p=1e9+7;
int f[101],n,ans[101],sum;
int gcd(int a,int b)
{
	if(b==0)
	{
		return a;
	}
	return gcd(b,a%b);
}
int lcm(int a,int b)
{
	return a/gcd(a,b)*b;
}
int power(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1)
		{
			res=res*a%p;
		}
		a=a*a%p;
		b>>=1;
	}
	return res;
}
signed main()
{
	cin>>n;
	ans[2]=1;
	for(int i=3;i<=50;i++)
	{
		for(int j=2;j<=i;j++)
		{
			if(i%j)
			{
				ans[i]=ans[j]+1;
				break;
			}
		}
	}
	int g=1;
	for(int i=2;i<=min((long long)42,n);i++)
	{
		f[i]=n/g;
		if(g==1)
		{
			f[i]--;
		}
		int k=g;
		g=lcm(g,i);
		for(int j=2;j<=i;j++)
		{
			if(j%k==0&&j<g)
			{
				f[i]--;
			}
		}
		f[i]-=n/g;
	}
	sum=1;
	for(int i=2;i<=50;i++)
	{
		sum=sum*power(ans[i]+1,f[i])%p;
	//	cout<<f[i]<<" ";
	}
	cout<<sum;
	return 0;
}
2022/8/25 11:22
加载中...