当前位置:编程学习 > C/C++ >>

Problem 1010

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.zzzyk.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; 
}  

 作者:princeyuaner

补充:软件开发 , C++ ,
CopyRight © 2022 站长资源库 编程知识问答 zzzyk.com All Rights Reserved
部分文章来自网络,