专栏文章

题解：P6210 「SWTR-4」Easy Math Problems

wwwt100127
P6210题解参与者 2已保存评论 1

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
1 条
当前快照
1 份
快照标识符
@mipw2uqs
此快照首次捕获于
2025/12/03 18:53
3 个月前
此快照最后确认于
2025/12/03 18:53
3 个月前
查看原文

题意：（题目已经说得简洁了）

思路

我们发现其实只需求： 对于某个 mm，
∑i=1n [gcd⁡(d,n)≤c]\sum_{i = 1}^{n} \ [\gcd(d,n) \le c]
我们不妨令：
h(m)=[gcd⁡(d,n)≤c]h(m)= [\gcd(d,n) \le c] f(m)=∑i=1mh(d)f(m)= \sum_{i = 1}^{m} h(d)
显然 f(m)f(m) 单调不减，可以处理第一问。
当 d≥nd \ge n 时，gcd⁡(d,n)=gcd⁡(d mod n,n)\gcd(d,n)=\gcd(d \bmod n,n)，所以 h(m)h(m) 显然是周期性的，周期是 nn，所以就只需要考虑 m<nm<n 的情况就可以了。
f(m)=∑k∣n,k≤c∑k=1mk[gcd⁡(i,nk)=1]f(m)= \sum_{k \mid n,k \le c} \sum_{k=1}^{\frac{m}{k}} [\gcd(i,\frac{n}{k})=1]
枚举 gcd⁡(i,n/k)\gcd(i,n/k) 得：
f(m)=∑d=1n∑k∣n,k≤c∑i=1mk[d∣i][d∣nk]∗μ(d)f(m)= \sum_{d=1}^{n} \sum_{k \mid n,k \le c} \sum_{i=1}^{\frac{m}{k}} [d \mid i][d \mid \frac{n}{k}]*\mu(d)
令 d∗k=Td \ast k=T，显然有 mT\frac{m}{T} 个 ii 满足 d∣id \mid i。
所以
f(m)=∑k∣n,k≤c∑T∣nμ(d)∗mTf(m)= \sum_{k \mid n,k \le c} \sum_{T \mid n} \mu(d)*\frac{m}{T}
即
f(m)=∑T∣nmT∗∑k∣T,k≤cμ(Td)f(m)= \sum_{T \mid n} \frac{m}{T}* \sum_{k \mid T,k \le c} \mu(\frac{T}{d})
令 g(T)=∑d∣T,d≤cμ(Td)g(T)=\sum_{d \mid T,d \le c}\mu(\frac{T}{d})。
那么现在考虑怎样求 gg，枚举 nn 的因数后爆算就行了。
感觉本题难点在高精度上
CPP
#include<bits/stdc++.h>
using namespace std;
int read(){ int x=0; bool flag=1; char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-') flag=0;ch=getchar();}
	while(ch>='0' && ch<='9'){x=(x<<3)+(x<<1)+(ch^48);ch=getchar();}
	return flag? x:-x;}
const int maxn=1e7+5;
const int SIZE_BIG=1e5+5;
int n,m,c;

int Mu[maxn],Yi[1005];
int F[maxn],g[1005];
int Prime[maxn],cnt;
bool vis[maxn];
void init()
{
	int i,j,num=0;
	Mu[1]=1;
	for(i=2;i<=n;i++)
	{
		if(vis[i]==0)
		{
			Prime[++cnt]=i;
			Mu[i]=-1; 
		}
		for(j=1;j<=cnt && i*Prime[j]<=n;j++)
		{
			vis[i*Prime[j]]=1;
			if(i%Prime[j]==0)
			{
				Mu[i*Prime[j]]=0;
				break;
			}
			Mu[i*Prime[j]]=-Mu[i];
		}
	}
	
	for(i=1;i*i<=n;i++)
	{
		if(n%i==0)
		{
			Yi[++num]=i;
			Yi[++num]=n/i;
		}
	}
	sort(Yi+1,Yi+1+num);
	num=unique(Yi+1,Yi+1+num)-Yi-1;
	for(i=1;i<=num;i++)
	{
		if(Yi[i]>c) break;
		for(j=i;j<=num;j++)
		{
			if(Yi[j]%Yi[i]==0)
			g[j]+=Mu[Yi[j]/Yi[i]];
		}
	}
	for(i=1;i<=num;i++)
	{
		for(j=Yi[i];j<=n;j+=Yi[i])
		F[j]+=g[i];
	}
	for(i=1;i<=n;i++) F[i]+=F[i-1];
}

char s[SIZE_BIG];
struct Big
{
	int a[SIZE_BIG],len;
	void Clear(){memset(a,0,sizeof(a));len=0;}
	void clear(){while(len>1 && a[len]==0) len--;}
	void read()
	{
		scanf("%s",s+1);
		len=strlen(s+1);
		for(int i=1;i<=len;i++)
		a[i]=(s[len-i+1]^48);
	}
	void write()
	{
		clear();
		for(int i=len;i>=1;i--)
		putchar(a[i]+48);
		putchar('\n');
	}
	int &operator [](int i){return a[i];}
	Big friend operator +(Big a,int b)
	{
		int i; a[1]+=b;
		for(i=1;i<=a.len;i++)
		{
			if(a[i]>=10)
			{
				a[i+1]+=a[i]/10;
				a[i]%=10;
				if(i==a.len)
				a.len++;
			}
		}
        a.clear();
		return a;
	}
	Big friend operator -(Big a,int b)
	{
		int i; a[1]-=b;
		for(i=1;i<=a.len;i++)
		{
			if(a[i]<0)
			{
				a[i]+=10;
				a[i+1]--;
			}
		}
		a.clear();
		return a;
	}
	Big friend operator -(Big a,Big b)
	{
		int i;
		for(i=b.len;i>=1;i--) a[i]-=b[i];
		for(i=1;i<=a.len;i++)
		{
			if(a[i]<0)
			{
				a[i]+=10;
				a[i+1]--;
			}
		}
		a.clear();
		return a;
	}
	Big friend operator *(Big a,int b)
	{
		int i;
		for(i=1;i<=a.len;i++) a[i]*=b;
		for(i=1;i<=a.len;i++)
		{
			if(a[i]>=10)
			{
				a[i+1]+=a[i]/10;
				a[i]%=10;
				if(i==a.len)
				a.len++;
			}
		}
		return a;
	}
	Big friend operator /(Big a,int b)
	{
		int i,x=0;
		for(i=a.len;i>=1;i--)
		{
			x=x*10+a[i];
			a[i]=x/b;
			x%=b;
		}
        a.clear();
		return a;
	}
	int friend operator %(Big a,int b)
	{
		int i,x=0;
		for(i=a.len;i>=1;i--)
		{
			x=x*10+a[i];
			a[i]=x/b;
			x%=b;
		}
		return x;
	}
}f,ans,L,R,Ans;
signed main()
{
	int i,kkk=0;
	n=read(),c=read(); init();
	f.read(); ans=f/F[n]*n; kkk=f%F[n];
	if(kkk==0)
	{
		ans=ans-n;
		for(i=n;i>=1;i--)
		{
			if(F[i]!=F[n])
			{
				ans=ans+(i+1);
				break;
			}
		}
	}
	else
	{
		for(i=0;i<n;i++)
		{
			if(kkk==F[i])
			{
				ans=ans+i;
				break;
			}
		}
	}
	ans.write(); ans.Clear();
	f.read(); f=f-1; kkk=f%n;
	ans=f/n*F[n]+F[kkk];
	f.Clear(); f.read(); kkk=f%n;
	Ans=f/n*F[n]+F[kkk];
	ans=Ans-ans; ans.write();
	return 0;
}

评论

共 1 条评论，欢迎与作者交流。

正在加载评论...