「BZOJ 3813」奇数国

发表于 | | 阅读次数:
字数统计: 1k 字

Description

题目链接：BZOJ 3813

在一片美丽的大陆上有 $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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
 
#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;
}
0%