Chokudai Speed Run G問題
Chokudai Speed Run001 G問題解説
問題
数列 aが与えられ a を連結させた整数を、 1,000,000,007 で割った余りを求めなさい。
サンプル
Input
7
7 6 5 4 3 2 1
Output
7654321
解説
全てを加えて剰余をとるという方針はlong long では所持できないので不可能です
そこで剰余の性質の以下2つを使います。
(x*y)%MOD = ( (x%MOD) * (y%MOD) ) % MOD
(x+y)%MOD = ( (x%MOD) + (y%MOD) ) % MOD
この二つの性質を使うことによって桁を一つづつ見ていくことによって連結した数列の剰余を正しく求めることができます。
以下コード
#include <iostream> using namespace std; #define MOD 1000000007 int main(void){ int n; string s; cin >> n; for(int i=0; i<n; i++){ string tmp; cin >> tmp; s += tmp; } long long ans = 0; for(int i=0; i<s.length(); i++){ ans = ans * 10 + (s[i]-'0'); ans %= MOD; } cout << ans << endl; return 0; }