Fork me on GitHub

Uoj#38.【清华集训2014】奇数国

Uoj#38. 【清华集训2014】奇数国

题意:

  • 有$n$个数,开始每个数均为$3$。
  • 有两种操作:
    • 修改某个数。
    • 查询区间乘积的欧拉函数值。
  • 保证每个数只包含前$60$个质因子。
  • $1\le n\le 10^5$。

题解:

  • 一个数$x$的欧拉函数值可以表示为$x\times \prod_{P_i|x}\frac{P_i-1}{P_i}$。
  • 所以维护区间乘积以及一段区间出现的质数集合即可。
  • 开两棵线段树维护,复杂度$O(60n+n\log n)$。

代码:

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
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#define ll long long
#define gc getchar()
#define N 100001
#define mod 19961993
using namespace std;
int a[60]={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};
ll root[2],lson[N*10][2],rson[N*10][2],cnt,ans[N*10][2],inv[300];
ll read()
{
ll x=0,f=1;
char ch;
for (;ch<'0'||ch>'9';ch=gc)
if (ch=='-') f=-1;
for (;ch>='0'&&ch<='9';ch=gc)
x=x*10+ch-'0';
return x*f;
}
ll get(ll x)
{
int i=0;
int Ans[60];
for (int i=0;i<60;i++) Ans[i]=0;
ll sum=0;
while (x>1)
{
while (x%a[i]==0) Ans[i]++,x/=a[i];
if (Ans[i]) sum|=1ll<<i;
while (i<60&&x%a[i]) i++;
}
return sum;
}
void ins(int l,int r,int x,ll &cur,int k,ll val)
{
if (!cur) cur=++cnt;
if (l==r)
{
ans[cur][k]=val;
return;
}
int mid=l+r>>1;
if (x<=mid) ins(l,mid,x,lson[cur][k],k,val);
else ins(mid+1,r,x,rson[cur][k],k,val);
if (k==0) ans[cur][k]=(ll)ans[lson[cur][k]][k]*ans[rson[cur][k]][k]%mod;
else ans[cur][k]=(ll)ans[lson[cur][k]][k]|ans[rson[cur][k]][k];
}
ll qry(int l,int r,int L,int R,ll cur,int k)
{
if (L<=l&&R>=r) return ans[cur][k];
int mid=l+r>>1;
ll sum=0;
if (L<=mid) sum=qry(l,mid,L,R,lson[cur][k],k);
if (R>mid)
{
if (k==0)
{
if (sum)
sum=(ll)sum*qry(mid+1,r,L,R,rson[cur][k],k)%mod;
else
sum=qry(mid+1,r,L,R,rson[cur][k],k)%mod;
}
else
sum|=qry(mid+1,r,L,R,rson[cur][k],k);
}
return sum;
}
int main()
{
inv[1]=1;
for (int i=2;i<300;i++)
inv[i]=(mod-mod/i)*inv[mod%i]%mod;
ll m=read();
for (int i=1;i<=100000;i++)
ins(1,100000,i,root[0],0,3),ins(1,100000,i,root[1],1,2);
for (int i=1;i<=m;i++)
{
ll x=read(),y=read(),z=read();
if (x==1)
{
ll A=get(z);
ins(1,100000,y,root[0],0,z);
ins(1,100000,y,root[1],1,A);
}
else
{
ll A=qry(1,100000,y,z,root[0],0);
ll B=qry(1,100000,y,z,root[1],1);
for (int j=0;j<60;j++)
{
ll k=1ll<<j;
if (k&B)
A=A*(a[j]-1)%mod*inv[a[j]]%mod;
}
printf("%d\n",A);
}
}
return 0;
}
-------------本文结束感谢您的阅读-------------

本文标题:Uoj#38.【清华集训2014】奇数国

文章作者:wzf2000

发布时间:2018年04月18日 - 15:04

最后更新:2018年04月27日 - 11:04

原始链接:https://wzf2000.github.io/2018/04/18/Uoj38/

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。