Problem 22218 --NOI2014湖北省选一试第3题 超能粒子炮

22218: NOI2014湖北省选一试第3题 超能粒子炮

Time Limit: 2 Sec  Memory Limit: 256 MB
Submit: 1  Solved: 1
[Submit][Status][Web Board][Creator:][下载FPS2元][添加到购物车][下载测试数据2元][172kb]

Description

邪恶的巨型宇宙怪物CCMCrazy Code Monster)即将对美丽的地球发动攻击!在这千钧一发的时刻,地球联合军决定使用地球最先进的能量武器——由发明家SHTSC设计的超能粒子炮彻底摧毁CCM

超能粒子炮由垂直方向从上到下共n个超能粒子发射管构成,编号1~n。所有的发射管都会在开火的一瞬间同时发射出强大的超能粒子流。为了彻底摧毁再生能力极强的邪恶宇宙怪物CCM,地球联合军将CCM从上到下分为m个区域,编号1~m,分别进行打击。其中超能粒子炮的第i号发射管将会对准f(i)号区域发射。f(i) 的公式如下:

f(i)=(a·i+b)mod m+1

其中ab都是给定的常数。

然而,出于某种不可告人的目的,N财团不希望CCM被超能粒子炮彻底消灭。于是N财团以远程精神控制了超能粒子炮的操作员——你来阻止地球军消灭CCM

你发现,超能粒子炮的开火模式会使得不同的粒子流的运动轨迹发生交叉,而在所有这些交叉点处部署一种名为折跃棱镜的能量反射装置就能使得超能粒子炮因过载而自爆。这样,你就可以阻止地球联合军使用超能粒子炮摧毁CCM而成为下一代N财团金牌的获得者。

为了实现这个计划,你需要知道有多少对粒子流i, j,满足i<jf(i) > f(j)

Input

第一行四个整数:n, m, a, b。分别为超能粒子炮的发射管数目、CCM被分成的区域数、以及题目描述中的f公式中的常数。

【数据规模】

对于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’} ≤1000a,b<mm是质数。


Output

输出一行一个整数,为运动轨迹交叉的粒子流的对数。

blaster1.in

blaster1.out

2 3 2 2

1

 

blaster2.in

blaster2.out

5 5 2 0

 

7


Sample Input

2 3 2 2

Sample Output

1

HINT

Source

[Submit][Status]