哈工大

Description

男从戎，女守家。一夜，狼烟四起，男战死沙场。从此一道黄泉，两地离别。最后，女终于在等待中老去逝去。逝去的最后是换尽一生等到的相逢和团圆。

某日两人至奈何桥前，服下孟婆汤。

每滴孟婆汤都有强度不一的药效，设一碗孟婆汤共N滴(0＜N＜100000)，其中第i滴（0≤i＜N）用b[i]表示。

孟婆汤的药效与原料有关，设熬制前同样有N滴原料，第i滴原料用a[i]表示，0≤a[i]＜2^32。

药效b[i]的计算方法为b[i]=(a[0]*a[1]*...*a[N-1]/a[i])%m（假设0/0=1），0＜b[i]＜2^32。

Input

多组输入数据。

每组第一行给出原料数量N，取模数m，紧接着的一行按顺序给出原料a[i]。

Output

求出熬制所成每份孟婆汤的药效b[i]，每份之间用空格隔开，每组数据之后以换行结尾。

Sample Input

5 11

2 7 5 3 9

3 7

9 8 5

Sample Output

10 6 4 3 1

5 3 2

Source

2014 Winter Holiday Contest 2

第一眼我们就能看出来 b[i]就是除了a[i]项之外所有的项相乘；

肿么办？？

求每个元素都便利一遍？肯定是不行的时间复杂度o（n*n） 额……

所以肯定不能那么暴力

不过 我们这样想 b[i]不就是前面的乘积乘上后面的乘积吗 就差一点就找到出路了

是不是很兴奋 啊啊啊啊啊 是啊

我们可以开两个数组 :

第一个数组 第i项表示前i项的乘积 

的二个数组 第i项表示i+1项到最后一项的乘积

问题迎刃而解 时间复杂度完全降下来

#include<cstdio>
const int N=100010;
long long a[N],b[N],c[N];
int main()
{int n,i,j;long long m;while(scanf("%d%lld",&n,&m)!=EOF){b[0]=1;for(i=1;i<=n;i++){scanf("%d",&a[i]);a[i]%=m;b[i]=b[i-1]*a[i];b[i]%=m;}c[n+1]=1;for(i=n;i>=1;i--){c[i]=c[i+1]*a[i];c[i]%=m;}printf("%lld",c[2]);for(i=2;i<=n;i++)printf(" %lld",b[i-1]*c[i+1]%m);printf("\n");}return 0;
}