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$ である.(例は問題文原文を参照)
$a_k$ の桁数を $d_k$ とする.
また,$a_k$ が始まる桁数,つまり,それ以降に何桁あるかを
$\displaystyle s_k = \sum_{i=k+1}^N d_i L_i $
とする.
各パートについて,$a_k 10^{s_k} c_k$ を ${\rm mod}\ B$ で求めれば良い.
ここで,$c_k = 1 + 10^{d_k} + 10^{2d_k} + \cdots + 10^{(L_k-1)d_k}$である.
ここで,$s_k$ は下から順番に計算すれば良いので,計算が難しいのは $c_k$ になる.
そこで,$f(m, p) = 1 + m + m^2 + \cdots + m^{p-1}$ の計算方法を考える.
これは,べき乗を高速に求めるのと同じような感じで計算できる.
$m$ が奇数の時は,$f(m,p) = m f(m-1,p) + 1$ で,
$m$ が偶数の時は,$f(m,p) = (p^{m/2}+1) f(m/2,p)$ と,再帰的に計算すれば良い.
#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年04月27日04時22分39秒
Last modified: 2014年03月30日00時17分10秒 (by laycrs)
Tags: Competitive_Programming AtCoder AtCoder_Regular_Contest ARC020 ARC_C
トップページに戻る
Logged in as: unknown user (not login)