問題はこちら
No.220 世界のなんとか2 - yukicoder
よく考察すると難しい計算はしなくて良い事がわかる
10^Pは該当しないので、必要なら上位にleading zeroをつけることで「ちょうどP桁の数のうち条件を満たすものは何個あるか？（ただし0を除く）」という問題だと読み替えられる
条件を満たさないものの個数を数えることにする
3のつかない数は明らかに9^P個なので、この内さらに3の倍数でないものがいくつあるか考える
数X'をP-1桁で、3のつかない数とする。この数の最上位に1桁数字をつけてP桁の数Xを作ることを考える
付け加える数字は0～2,4～9の9個の中から選ぶことになるが、この中には3で割ったあまりが0,1,2になるものがそれぞれ3個ずつあるので、Xを3の倍数とするようなものはX'によらずちょうど3個あることが分かる。
よってP桁の条件を満たさないものの個数は9^(P-1)*6となり、求めるべき答えは10^P-(9^(P-1)*6+1)となる
（+1は0の分）
powを使うと精度が足りないので整数で計算する
long po(int x,int a){return a==0?1:x*po(x,a-1);} int main(){ int p; scanf("%d",&p); printf("%ld",po(10,p)-po(9,p-1)*6-1); return 0; }
ぎゅっと
n; long p(a,b){return b?a*p(a,b-1):1;} main(){n=scanf("%d",&n)>printf("%ld",p(10,n)-p(9,n-1)*6-1);}
97B
