本文主要是介绍COJ 1163: 寒衣调，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
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]。求出熬制所成孟婆汤的药效b[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
这题写得非常有范是吧？问题主要涉及扩展欧几里得算法和乘法逆元的一些问题，下面直接上代码了：
#include<cstdio>
#define MAXN 100005
int a[MAXN], b[MAXN];
int N, m;
int main()
{while(scanf( "%d%d", &N, &m) == 2){for(int i = 0; i < N; i++) scanf("%d",&a[i]);b[N] = 1;for(int i = N - 1; i >= 0; i --)b[i] = (long long)b[i + 1] * a[i] % m;for(int i = 1; i < N; i ++)a[i] = (long long)a[i - 1] * a[i] % m;printf( "%lld", (long long)b[1]);for(int i = 1; i < N; i ++)printf(" %lld", (long long)a[i - 1] * b[ i + 1] % m);printf("\n");}return 0;
}这篇关于COJ 1163: 寒衣调的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
