Jzoj 5425数論

賢い0 v 0はモビウスの反転を勉強しています.彼女はこのような問題を見た:n*m個人がn*mの方陣に立った......
残りの問題面は、賢い0 v 0は覚えていません.
しかし、彼女は自分の優れた数論の技巧を通じて、1つの転化後の模型を提供しました:nとmを与えて、求めます
ΣΣmin(n/i,m/j)*[gcd(i,j)=1]{1<=i<=n,1<=j<=m}
賢い0 v 0はもちろんどうすればいいか知っていますが、彼女はあなたを試験したいと思っています.
反転問題でも、杜教ふるいでもブロックでもいいです.
反転しないでどうする?
gcd(i,j)=1は傾きを表すものと見なすことができることを見出した.
一方min(n/i,m/j)は2次元区間[1,n][1,m]における直線の整点個数である
だから答えはn*m
コードは一人の大物を貼って反転させよう、コードfromBAJimH

#include 
#include 
#include 
#include 
#include 
#include 
#define fo(i,a,b) for(int i=a;i<=b;i++)
#define fod(i,a,b) for(int i=a;i>=b;i--)
#define N 10000005
#define LL long long
using namespace std;
LL mo,pr[N],su[N],s[N];
int n,m,l;
bool bz[N];
void prp()
{
	su[1]=1;
	fo(i,2,n)
	{
		if(!bz[i]) pr[++l]=i,su[i]=-1;
		for(int j=1;j<=l&&pr[j]*i<=n;j++)
		{
			bz[i*pr[j]]=1;
			if(i%pr[j]==0) break;
			su[i*pr[j]]=-su[i];
		}
		(su[i]+=su[i-1])%=mo;
	}
}
LL get(LL n,LL m)
{
	if(n==0) return 0;
	LL d1=m/(m/n);
	return (s[d1]-(d1-n)*(m/n)%mo)%mo;
	
}
void fd(LL m)
{
	s[0]=0;
	LL d=1;
	while(d<=m)
	{
		LL d1=m/(m/d);
		s[d1]=(s[d-1]+(d1-d+1)*(m/d)%mo)%mo;
		d=d1+1;
	}
}
int main()
{
	freopen("math.in","r",stdin);
	freopen("math.out","w",stdout);
	cin>>n>>m>>mo;
	if(n1,ans=0;
	while(d<=m)
	{
		LL d1=min(n/(n/d),m/(m/d)),i=1,s1=0;
		fd(m/d);
		while(i<=n/d)
		{
			LL i1=(n/d)/(n/d/i),j=(m/d)/(n/d/i);
			(s1+=(LL)(i1-i+1)%mo*(j*(n/d/i)%mo+get(m/d,m/d)-get(j,m/d)))%=mo;
			i=i1+1;
		}
		(ans+=s1*(su[d1]-su[d-1])%mo)%=mo;
		d=d1+1;
	}
	printf("%lld
",(ans+mo)%mo);
}

転載先:https://www.cnblogs.com/Extended-Ash/p/9477222.html