#PQJ2728x15260. QOJ 2728_15260
QOJ 2728_15260
SHTSC2014 Day 1 超能粒子炮 blaster 【问题描述】 邪恶的巨型宇宙怪物CCM(Crazy Code Monster)即将对美丽的地球发动攻 击!在这千钧一发的时刻,地球联合军决定使用地球最先进的能量武器——由 发明家SHTSC 设计的超能粒子炮彻底摧毁CCM。 超能粒子炮由垂直方向从上到下共n 个超能粒子发射管构成,编号1~n。所 有的发射管都会在开火的一瞬间同时发射出强大的超能粒子流。为了彻底摧毁 再生能力极强的邪恶宇宙怪物CCM,地球联合军将CCM 从上到下分为m 个区 域,编号1~m,分别进行打击。其中超能粒子炮的第i 号发射管将会对准f(i)号 区域发射。f(i) 的公式如下: 𝑓(𝑖) = (𝑎∙𝑖+ 𝑏) 𝑚𝑜𝑑 𝑚+ 1 其中a,b 都是给定的常数。 然而,出于某种不可告人的目的,N 财团不希望CCM 被超能粒子炮彻底消 灭。于是N 财团以远程精神控制了超能粒子炮的操作员——你来阻止地球军消 灭CCM。 你发现,超能粒子炮的开火模式会使得不同的粒子流的运动轨迹发生交叉, 而在所有这些交叉点处部署一种名为折跃棱镜的能量反射装置就能使得超能粒 子炮因过载而自爆。这样,你就可以阻止地球联合军使用超能粒子炮摧毁 CCM 而成为下一代N 财团金牌的获得者。 为了实现这个计划,你需要知道有多少对粒子流i, j,满足i<j 且f(i) > f(j)。 【输入文件】 第一行四个整数:n, m, a, b。分别为超能粒子炮的发射管数目、CCM 被分 成的区域数、以及题目描述中的f 公式中的常数。 【输出文件】 输出一行一个整数,为运动轨迹交叉的粒子流的对数。
SHTSC2014 Day 1 【输入输出样例】 blaster1.in blaster1.out 2 3 2 2 1 blaster2.in blaster2.out 5 5 2 0 7 【数据规模】 对于10%的数据,n≤5000。 对于20%的数据,n≤m≤106。 对于额外20%的数据,b=0。 对于80%的数据,1≤a≤1000。 对于100%的数据,n≤m≤109,存在a’满足a*a’=1 (mod m) , 且min{a,a’} ≤1000,a,b<m,m 是质数。