1105-Unable Count
http://rose.u-aizu.ac.jp/onlinejudge/ProblemSet/description.jsp?id=1105
問題概要
3つの整数n,a,bが与えられる。
n以下の整数のうち、a*i+b*j(i,jは0含む自然数)で表現出来ないものの個数を求めよ。
考え方
エラトステネスの篩みたいな感じで、i番目の数で生成可能ならi+a番目とi+b番目も可能という風にしていく。
実装(C++)
#include <iostream> #include <vector> using namespace std; int main() { int n,a,b,ans; for(;cin>>n>>a>>b;){ if(n==0)break; n++; ans=0; vector<bool> chk(n); chk[0]=true; if(a<n)chk[a]=true; if(b<n)chk[b]=true; for(int i=0;i<n;i++){ if(!chk[i]){ ans++; }else{ if(i+a<n)chk[i+a]=true; if(i+b<n)chk[i+b]=true; } } cout<<ans<<endl; } return 0; }