程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Problem 1010

Problem 1010

編輯：C++入門知識

Description
給出數列A1;A2; : : : ;AN，並設

現要求把所有的Bi 算出來。
Input
輸入包含多組測試數據。對於每組數據，第1 行，1 個整數N(1 <= N <= 100 000), 表示數列的長度。第2
行，N 個整數A1,A2, ......,AN(1 <= Ai <= 109)，表示給出的數列。輸入以一個0 表示結尾。
Output
對於每組數據，輸出一行，N 個整數用空格分隔，表示算出的B1,B2, ....,BN。

Sample Input
3
1 2 3
0
Sample Output
6 3 2
這個題目最重要的就是要知道 abc%mod = （ab%mod * c）%mod，知道了這個應該就不是很難了。
[cpp]
#include<iostream>
#include<stdio.h>
using namespace std;

const int N = 11111;
const int MOD = 1000000007;

int n, a[N], preffix[N], suffix[N];

int multiply (int a,int b){
    return (long long)a * b % MOD;//進行a*b%MOD的函數
    }

int main(){//假設現在有abcdef這麼多的數
    while(scanf("%d",&n) == 1 && n){
        for(int i = 1;i <= n; i++){
            scanf("%d",&a[i]); www.2cto.com
            }
            preffix[0] = 1;
            for(int i = 1;i <= n; i++){
                preffix[i] = multiply(preffix[i-1],a[i]); //把1*a%MOD,ab%MOD,abc%MOD........的結果保存下來
                }
                suffix[n+1] = 1;
                for(int i = n ;i >= 1; i--){
                    suffix[i] = multiply(suffix[i+1],a[i]); //把......bcdef%MOD，abcdef%MOD的結果保存下來
                    }
                    for(int i = 1;i <= n; i ++){
                        printf("%d%c",multiply(preffix[i-1],suffix[i+1]),i == n? '\n':' ');//假設此時的i=2；則這一步的運算就是acdef%MOD。
                        }
        }
        return 0;
}