题意分析

就是让你求

\[\sum_{i=1}^{|S|}val[i][gcd(a[i],x)=y]
\]

那么接下来就是化简式子

\[\sum_{i=1}^{|S|}val[i][gcd(\frac{a[i]}{y},\frac{x}{y})=1]
\]

\[\sum_{i=1}^{|S|}val[i]\sum_{d|\frac{a[i]}{y}d|\frac{x}{y}}μ(d)
\]

\[\sum_{i=1}^{|S|}val[i]\sum_{dy|a[i]dy|x}μ(d)
\]

我们考虑枚举\(x\)的因子\(k=dy\)

那么贡献就是\(μ(\frac{k}{y})*s[i]\)

其中\(s[i]=\sum_{i|d}val[d]\)

这里直接让\(val[a[i]]=val[i]\)了

然后查询修改我们都可以\(\sqrt n\)了

CODE:

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<cstdlib>

#include<string>

#include<queue>

#include<map>

#include<stack>

#include<list>

#include<set>

#include<deque>

#include<vector>

#include<ctime>

#define ll long long

#define inf 0x7fffffff

#define N 10000008

#define IL inline

#define M 1008611

#define D double

#define maxn 10000000

#define mod 20020303

#define R register

using namespace std;

template<typename T>IL void read(T &_)

{

    T __=0,___=1;char ____=getchar();

    while(!isdigit(____)) {if(____=='-') ___=0;____=getchar();}

    while(isdigit(____)) {__=(__<<1)+(__<<3)+____-'0';____=getchar();}

    _=___ ? __:-__;

}

/*-------------OI使我快乐-------------*/

int n,m,tot;

struct Node

{

	int xx,yy;

}e[M];

int prime[N],mul[N],val[N];

ll sum[N];

bool mark[N];

IL void work()

{

	mul[1]=1;

	for(R int i=2;i<=maxn;++i)

	{

		if(!mark[i]) {prime[++tot]=i;mul[i]=-1;}

		for(R int j=1;j<=tot&&prime[j]*i<=maxn;++j)

		{

			mark[prime[j]*i]=1;

			if(i%prime[j]==0)

			{

				mul[prime[j]*i]=0;

				break;

			}

			else mul[prime[j]*i]=-mul[i];

		}

	}

}

int main()

{

	freopen("t1.in","r",stdin);

	freopen("t1.out","w",stdout);

	read(n);read(m);work();

	for(R int i=1,x,y;i<=n;++i)

	{

		read(x);read(y);

		val[x]=y;

	}

	for(R int i=1;i<=maxn;++i)

	 for(R int j=i;j<=maxn;j+=i)

	  sum[i]+=val[j];

	while(m--)

	{

		int knd,x,y;ll ans=0;

		read(knd);read(x);read(y);

		if(knd==1)

		{

			for(R int i=1;i*i<=x;++i)

			{

				if(x%i) continue;

				int cdy=i,wzy=x/i;

				if(cdy%y==0)

				{

					int now=cdy/y;

					ans=(ans+mul[now]*sum[cdy]%mod+mod)%mod;

				}

				if(cdy==wzy) continue;

				if(wzy%y==0)

				{

					int now=wzy/y;

					ans=(ans+mul[now]*sum[wzy]%mod+mod)%mod;

				}

			}

			printf("%lld\n",ans);

		}

		else

		{

			if(val[x])

			{

				for(R int i=1;i*i<=x;++i)

				{

					if(x%i) continue;

					int cdy=i,wzy=x/i;

					sum[cdy]-=val[x];

					if(cdy==wzy) continue;

					sum[wzy]-=val[x];

				}

				val[x]=0;

			}

			else

			{

				val[x]=y;

				for(R int i=1;i*i<=x;++i)

				{

					if(x%i) continue;

					int cdy=i,wzy=x/i;

					sum[cdy]+=val[x];

					if(cdy==wzy) continue;

					sum[wzy]+=val[x];

				}

			}

		}

	}

	fclose(stdin);

	fclose(stdout);

    return 0;

}

巴特西

考试题 T1

题意分析

CODE:

HEOI 2019 RP++

最新文章

热门文章