自动搬运

查看原文

来自洛谷，原作者为

	Siyuan Dream OIer.

搬运于2025-08-24 21:56:55，当前版本为作者最后更新于2019-02-08 10:52:09，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

$$\Large\texttt{My Blog}$$

Description

题目链接：Luogu 4140

在一片美丽的大陆上有 $100000$ 个国家，每个国家有一个银行。某大公司的领袖在这 $100000$ 个银行开户时都存了 $3$ 大洋，他惜财如命，因此会不时地派小弟 GFS 清点一些银行的存款或者让 GFS 改变某个银行的存款。这里发行的软妹面额是最小的 $60$ 个素数，任何人的财产都只能由这 $60$ 个基本面额表示。

领袖习惯将一段编号连续的银行里的存款拿到一个账房去清点。如果领袖选择清点编号在 $[a,b]$ 内的银行财产，他会先对 $[a,b]$ 的财产求和（计为 $\text{product}$），然后在编号属于 $[1,\text{product}]$ 的账房中选择一个去清点存款。一个账房 $\text{number}$ 可能被选中当且仅当 $\gcd(\text{product},\text{number})=1$。当领袖又赚大钱了的时候，他会在某个银行改变存款，但是领袖不会在某个银行的存款总数超过 $10^6$。

现在 GFS 预先知道了领袖的清点存款与变动存款的 $x$ 次计划，想请你告诉他，每次清点存款时领袖有多少个账房可以供他选择，当然这个值可能非常大，GFS 只想知道对 $19961993$ 取模后的答案。

数据范围：$1\le x\le 10^5$

Solution

我们注意到，每个数的标准分解形式中只有可能出现前 $60$ 个数字，那么我们考虑用线段树维护区间内每个质因子是否出现过（笔者使用压位，用 $\text{long long}$ 储存，操作起来较为简单），并维护区间内的乘积。统计答案时，我们只需要求出区间的乘积的 $\varphi$ 函数值即可。

时间复杂度：$O(60\cdot m\log n)$

Code

#include <cstdio>
#include <algorithm>
#define lson p<<1
#define rson p<<1|1

const int prime[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,227,229,233,239,241,251,257,263,269,271,277,281};
const int invpr[]={9980997,6653998,11977196,8555140,5444180,1535538,10568114,14708837,3471651,11701858,17386252,1618540,16066970,2321162,18263100,16948862,12518538,15380552,10725847,1686929,13399146,17182475,12025297,15924736,13582387,395287,6395590,15857658,16299242,6359573,3300802,18742940,6702567,10914471,16210746,11765678,5340151,18247466,7769638,8077107,11932588,6506948,1985748,6619521,5877135,4413707,9744480,10115270,14597757,16475182,18334191,5011379,18885205,7555336,621385,11309266,12170137,12006660,18304499,11153142};
const int N=1e5+5;
const int mod=19961993;
int n=100000,m,a[N],mul[N<<2];
long long seg[N<<2];

void pushup(int p) {
	seg[p]=seg[lson]|seg[rson];
	mul[p]=1LL*mul[lson]*mul[rson]%mod;
}
void modify(int x,int p,int l,int r,long long f,int v) {
	if(l==r) {
		seg[p]^=f,mul[p]=v;
		return;
	}
	int mid=(l+r)>>1;
	if(x<=mid) modify(x,lson,l,mid,f,v);
	else modify(x,rson,mid+1,r,f,v);
	pushup(p);
}
long long queryFac(int x,int y,int p,int l,int r) {
	if(x<=l&&r<=y) return seg[p];
	int mid=(l+r)>>1;
	long long ans=0;
	if(x<=mid) ans|=queryFac(x,y,lson,l,mid);
	if(mid<y) ans|=queryFac(x,y,rson,mid+1,r);
	return ans;
}
int queryMul(int x,int y,int p,int l,int r) {
	if(x<=l&&r<=y) return mul[p];
	int mid=(l+r)>>1,ans=1;
	if(x<=mid) ans=1LL*ans*queryMul(x,y,lson,l,mid)%mod;
	if(mid<y) ans=1LL*ans*queryMul(x,y,rson,mid+1,r)%mod;
	return ans;
}
int query(int l,int r) {
	int ans=queryMul(l,r,1,1,n);
	long long f=queryFac(l,r,1,1,n);
	for(int i=0;i<60;++i) {
		if(f&(1LL<<i)) ans=1LL*ans*invpr[i]%mod*(prime[i]-1)%mod;
	}
	return ans;
}
void ins(int x,int val) {
	long long f=0;
	for(int i=0;i<60;++i) {
		if(val%prime[i]==0) f^=1LL<<i;#
	}
	modify(x,1,1,n,f,val);
}
int main() {
	for(int i=1;i<=n;++i) a[i]=3,modify(i,1,1,n,2,a[i]);
	for(scanf("%d",&m);m--;) {
		int o,x,y;
		scanf("%d%d%d",&o,&x,&y);
		if(o==0) {
			printf("%d\n",query(x,y));
		} else {
			ins(x,a[x]),ins(x,a[x]=y);
		}
	}
	return 0;
}