2014年03月30日00時01分15秒に更新されたバージョンを表示しています.
最新のページはこちらをご覧ください.
AtCoder Regular Contest #020
問題文
正の整数 $A,B$ が与えられるので $A\ {\rm mod}\ B$ を求める問題.
ただし,$A$ は特別な形式で与えられる.
$2$ つの $N$ 要素の正整数の列 $\{a_i\}_{i=1}^N, \{L_i\}_{i=1}^N$ が与えられる.
$a_1$ を $10$ 進数で書いたものを $L_1$ 個続けて書いて,
$a_2$ を $10$ 進数で書いたものを $L_2$ 個続けて書いて,…,
$a_N$ を $10$ 進数で書いたものを $L_N$ 個続けて書いたものを繋げたものが $A$ である.(例は問題文原文を参照)
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define ll long long
int digit(int a){
int res = 0;
while(a) res++, a/=10;
if(res==0) res++;
return res;
}
ll pw(ll a,ll b, ll md){
ll r;
if(!b) return 1;
r = pw(a,b/2,md);
r = (r*r)%md;
if(b%2) r = (r*a)%md;
return r;
}
ll solve(ll multi, ll n, ll md){
ll r = 0;
if(n==1) return 1;
if(n%2){
r = solve(multi, n-1, md) * multi + 1;
r %= md;
} else {
r = solve(multi, n/2, md) * (pw(multi, n/2, md) + 1);
r %= md;
}
return r;
}
int main(){
int N, B;
static int a[300000], L[300000];
int i, j, k;
ll res, dig, sod = 0, tmp;
scanf("%d",&N);
rep(i,N) scanf("%d%d",a+i,L+i);
scanf("%d",&B);
res = 0;
for(i=N-1;i>=0;i--){
dig = digit(a[i]);
tmp = a[i]; tmp %= B;
tmp *= pw(10, sod, B); tmp %= B;
tmp *= solve(pw(10, dig, B), L[i], B); tmp %= B;
res += tmp;
sod += L[i] * dig;
}
res %= B;
if(res < 0) res += B;
printf("%d\n",(int)res);
return 0;
}
Current time: 2024年05月08日05時32分29秒
Last modified: 2014年03月30日00時01分15秒 (by laycrs)
Tags: AtCoder AtCoder_Regular_Contest ARC020 ARC_C
トップページに戻る
Logged in as: unknown user (not login)