#1836. 奇数国
奇数国
奇数国
题目描述
全国信息学奥林匹克竞赛 第一试 奇数国 奇数国 【问题描述】 在一片美丽的大陆上有100000 个国家,记为1 到100000。这里经济发达, 有数不尽的账房,并且每个国家有一个银行。某大公司的领袖在这100000 个银 行开户时都存了3 大洋,他惜财如命,因此会不时地派小弟GFS 清点一些银行 的存款或者让GFS 改变某个银行的存款。该村子在财产上的求和(∑)运算等 同于我们的乘法(∏)运算,也就是说领袖开户时的存款总和为3100000。这里发 行的软妹面额是最小的60 个素数 (p1 = 2,p2 = ⋯… p60 = 281),任何人的财 产都只能由这60 个基本面额表示,即设某个人的财产为fortune(正整数),则 fortune = p1k1 ∗p2k2 ∗… ∗p60k60。 领袖习惯将一段编号连续的银行里的存款拿到一个账房去清点,为了避免 GFS 串通账房叛变,所以他不会每次都选择同一个账房。GFS 跟随领袖多年已经 摸清了门路,知道领袖选择账房的方式。如果领袖选择清点编号在 [a, b] 内的银 行财产,他会先对 [a, b] 的财产求和(计为product),然后在编号属于 [1, product] 的账房中选择一个去清点存款,检验自己计算是否正确同时也检验账房与GFS 是否有勾结。GFS 发现如果某个账房的编号number 与product 相冲,领袖绝对 不会选择这个账房。怎样才算与product 不相冲呢?若存在整数x,y 使得 number ∗x + product ∗y = 1,那么我们称number 与product 不相冲,即该账房 有可能被领袖相中。当领袖又赚大钱了的时候,他会在某个银行改变存款,这样 以来相同区间的银行在不同的时候算出来的product 可能是不一样的,而且领袖 不会在某个银行的存款总数超过1000000。 现在GFS 预先知道了领袖的清点存款与变动存款的计划,想请你告诉他, 每次清点存款时领袖有多少个账房可以供他选择,当然这个值可能非常大,GFS 只想知道对19961993 取模后的answer。 【输入格式】 从文件odd.in 中读入数据。 第一行一个数x 表示领袖清点和变动存款的总次数。 接下来 x 行,每行3 个数ai, bi, ci。ai 为0 时表示该条记录是清点计划,领 袖会清点bi 到ci 的银行存款,你需要对该条记录计算出GFS 想要的answer。ai 为1 时表示该条记录是存款变动,你要把银行bi 的存款改为ci ,不需要对该记 录进行计算。 【输出格式】 输出到文件odd.out 中。 输出若干行,每行一个数,表示那些年的answer。 第5 页 共6 页 全国信息学奥林匹克竞赛 第一试 奇数国 【样例输入】 6 0 1 3 1 1 5 0 1 3 1 1 7 0 1 3 0 2 3 【样例输出】 18 24 36 6 【样例说明】 初始化每个国家存款都为3; 1 到3 的product 为27,[1,27]与27 不相冲的有18 个数; 1 的存款变为5; 1 到3 的product 为45,[1,45]与45 不相冲的有24 个数; 1 的存款变为7; 1 到3 的product 为63,[1,63]与63 不相冲的有36 个数; 2 到3 的product 为9,[1,9]与9 不相冲的有6 个数。 【数据规模与约定】 20% 的数据满足:x ≤10000,当 ai = 0 时0 ≤ci −bi ≤100;每个 product ≤ 1018; 30% 的数据满足:x ≤50000;当 ai = 0 时 0 ≤ci −bi ≤10000; 50% 的数据满足:x ≤100000;当 ai = 0 时 0 ≤ci −bi ≤100000; 以上数据不重合,20%+30%+50%=100%,且保证满足题干要求。 第6 页 共6 页
输入格式
(见题面原文)
输出格式
(见题面原文)
数据范围
(见题面原文)
样例
样例 1
6
0 1 3
1 1 5
0 1 3
1 1 7
0 1 3
0 2 3
18
24
36
6