F - square1001の好きな回文数 (square1001's Favorite Palindrome)
解説
/
実行時間制限: 4 sec / メモリ制限: 256 MB
リジャッジをしました。申し訳ございません。(01/24 22:16:18追記)
部分点のケースはあっていますが、sub2-3.txtが間違っていることが判明しました。消去し次第リジャッジを行います。(01/24 22:12:49追記)
問題文
square1001の部分文字列である「1001」は回文数である。
すなわち、その名前を付けた彼も回文数が好きであった。
ということで、E869120は彼に次のような問題を出した。
「a以上b以下の数がある。 その中で、cの倍数かつ各位の数字の和が dである回文数はいくつあるか。」
square1001は、普通に全探索して求めようとしたが、 a , bが相当大きいためできなかった。
その問題の答えをmod 10000で求めよ。
入力
入力は以下の形式で標準入力から与えられる。
a b c d
正整数a,b,c,dが 1 行に入力される。
出力
条件を満たす回文数の個数を1行に出力せよ。
制約
- a<b
- 2≦|a|=|b|≦80 かつ |a|, |b|は2の倍数
- 1≦c≦50
- 1≦d≦720
- a,bは回文数
ここで, |a|はaの桁数を表す。
部分点
1≦a,b≦10,000,000,000を満たすデータセットすべてに正解した場合は、 20点が与えられる。
残りのデータセットすべてに正解した場合、80点が与えられる。
入力例1
1001 9999 9 36
出力例1
1
「9999」が条件を満たす。
入力例2
1001 4004 49 20
出力例2
1
「3773」が条件を満たす。
入力例3
1000000001 9999999999 50 50
出力例3
0
「0」で終わる回文数は存在しない。
問題文担当者:E869120