AtCoder Regular Contest #020 C問題 - A mod B Problem

Source

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)$ と,再帰的に計算すれば良い.

Cによるスパゲッティなソースコード

#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: 2017年11月21日04時15分56秒
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)

ログイン: