Codeforces Round #268 DIV1 C問題 (1500pt)
Codeforces Round #268 DIV2 E問題 (2500pt)
Problem description
$f(x)$ を $x$ を $10$ 進数で表記した時の数字の和とする.例えば,$f(112) = 1+1+2 = 4$.
正整数 $A$ が与えられるので
$\displaystyle \qquad \left(\sum_{x=L}^R f(x) \right)\ {\rm mod}\ A = 0$
となる $L,R$ を $1$ つ求める問題.
$L, R$ は $L < R$ で $10^{200}$ 未満でなければいけない.
答えが存在することは保証されている.
$\displaystyle \qquad g(l,r) =\sum_{x=l}^r f(x)$
と書くことにする.
色々あるけど,以下の方法でやった.
まず,大きい整数 $x$ に対して $g(0,x)$ を計算する方法は,桁ごとの周期性を利用して,$1$ の桁ではいくら,$10$ の桁ではいくら…,と計算すれば良い.
$g(x,y) = g(0,y) - g(0,x-1)$ なので,任意の $g(x,y)$ は高速に計算することができる.
$L=1$ として,$g(L,R) \geq A$ となる最小の $R$ を二分探索で求めた.
その後,$g(L,R) < A$ なら $R$ を $1$ 増やす,$g(L,R) > A$ なら $L$ を $1$ 増やす,$g(L,R) = 0$ になれば終了と,尺取法を行った.
$L$ や $R$ を $1$ 増やした時に $g(L,R)$ の値の変化は高々数十で,ランダムにそれぐらい変化すると思えば,高々 $100$ 回ぐらいの試行で $g(L,R) = A$ となるものが見つけるのは想像に難くない.
実際にどのようなケースでもその程度で終わるかどうかはよくわからないが,実際のところは大丈夫そう.
他の方法は,$k$ が高々 $18$ 桁の正整数の場合,$g(k,10^{18}+k-1)$ は $k$ が $1$ 増えると $1$ 増える.
よって,適当な $k$ に対して,$g(k, 10^{18}+k-1)$ を計算して,後どれぐらい増やせば ${\rm mod}\ A$ で $0$ になるかを調べれば良い.
$k=1$ とか $k=10^{18}+1$ の時などは,$g(k, 10^{18}+k-1)$ が簡単に計算できる.
#include<bits/stdc++.h>
using namespace std;
#define REP(i,a,b) for(i=a;i<b;i++)
#define rep(i,n) REP(i,0,n)
#define READER_BUF_SIZE 1048576
#define WRITER_BUF_SIZE 1048576
int reader_pt=READER_BUF_SIZE,reader_last;char reader_buf[READER_BUF_SIZE];
int writer_pt=0;char writer_buf[WRITER_BUF_SIZE];
#define mygc(c) {if(reader_pt==READER_BUF_SIZE)reader_pt=0,reader_last=fread(reader_buf,sizeof(char),READER_BUF_SIZE,stdin);(c)=reader_buf[reader_pt++];}
#define mypc(c) {if(writer_pt==WRITER_BUF_SIZE)writer_pt=0,fwrite(writer_buf,sizeof(char),WRITER_BUF_SIZE,stdout);writer_buf[writer_pt++]=(c);}
#define myed {fwrite(writer_buf,sizeof(char),writer_pt,stdout);writer_pt=0;}
#define ll long long
#define ull unsigned ll
void reader(int *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
void reader(int *x, int *y){reader(x);reader(y);}
void reader(int *x, int *y, int *z){reader(x);reader(y);reader(z);}
void reader(ll *x){int k,m=0;*x=0;for(;;){mygc(k);if(k=='-'){m=1;break;}if('0'<=k&&k<='9'){*x=k-'0';break;}}for(;;){mygc(k);if(k<'0'||k>'9')break;*x=(*x)*10+k-'0';}if(m)(*x)=-(*x);}
int reader(char c[]){int i,s=0;for(;;){mygc(i);if(i!=' '&&i!='\n'&&i!='\r'&&i!='\t'&&i!=EOF) break;}c[s++]=i;for(;;){mygc(i);if(i==' '||i=='\n'||i=='\r'||i=='\t'||i==EOF) break;c[s++]=i;}return s;}
void writer(int x, char c){int s=0,m=0;char f[10];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(ll x, char c){int s=0,m=0;char f[20];if(x<0)m=1,x=-x;while(x)f[s++]=x%10,x/=10;if(!s)f[s++]=0;if(m)mypc('-');while(s--)mypc(f[s]+'0');mypc(c);}
void writer(const char c[]){int i;for(i=0;c[i]!='\0';i++)mypc(c[i]);}
ll A;
ll L, R;
ll solve(ll N){
ll i, j, k, p;
ll res = 0;
p = 1;
for(;;){
if(N < p) break;
res += (N/(p*10)) * 45 * p;
k = N%(p*10);
rep(i,10){
j = min(p, k);
k -= j;
res += j * i;
}
p *= 10;
}
return res;
}
int main(){
int i, j, k;
ll lef, rig, cen;
ll val;
reader(&A);
L = 1;
lef = 0; rig = 20000000000000000LL;
while(lef < rig){
cen = (lef + rig) / 2;
R = cen;
val = solve(R+1) - solve(L);
if(val < A) lef = cen + 1; else rig = cen;
}
for(;;){
val = solve(R+1) - solve(L);
if(val==A) break;
if(val<A) R++;
else L++;
}
writer(L, ' ');
writer(R, '\n');
myed;
return 0;
}
Current time: 2024年04月26日18時37分44秒
Last modified: 2014年09月24日06時21分30秒 (by laycrs)
Tags: Competitive_Programming Codeforces CF268 CF_Div1_C CF_Div2_E
トップページに戻る
Logged in as: unknown user (not login)