読者です 読者をやめる 読者になる 読者になる

メモ

yukicoderで遊んでいる競プロゆるふわ勢

yukicoder No.220 世界のなんとか2

問題はこちら
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