#P3813. 奇数国

    ID: 3015 传统题 1000ms 256MiB 尝试: 1346 已通过: 489 难度: 6 上传者: 标签>CF1900提高欧拉函数普通线段树位集求并模逆元扩展欧几里得算法2015年国家集训队测试

奇数国

题目描述

给定一个初始值全为 33 的序列 a1⋯na_{1\cdots n},要求支持以下两种操作:

  • 0 l r,询问 φ(∏i=lrai)\varphi(\prod_{i=l}^r a_i);
  • 1 x y,ax←ya_x\gets y。

在本题中,n=105n=10^5,yy 的质因子只可能包含 6060 个质数。

输入格式

第一行一个整数 qq 表示操作次数。

接下来 qq 行,每行三个数表示一次操作,格式见题目描述。

输出格式

对于每次询问,输出一行一个整数表示答案对 1996199319961993 取模后的值。

6
0 1 3
1 1 5
0 1 3
1 1 7
0 1 3
0 2 3
18
24
36
6

数据规模与约定

对于 100%100\% 的数据,1≤q≤1051\leq q\leq 10^5,n=105n=10^5,yy 的质因子只可能包含前 6060 个质数,1≤x≤n1\leq x\leq n,1≤l≤r≤n1\leq l\leq r\leq n。

来源

20152015 年国家集训队测试。