Bình luận

• 
  

  0

  lehongduc    8:52 a.m. 22 Tháng 8, 2024

  hint

  dùng quay lui để vét cạn rồi tìm giá trị

  thuật toán

  theo đề ta có, số tiến đạt chỉ có nhiều nhất 13 chữ số và chỉ có 2 giá trị là 0 và 9
  vậy số phép tính tối đa là \(2^{13}\)=8192
  sau đó duyệt từ đầu tới cuối để tìm giá trị thỏa mãn chia hết cho n
  độ phức tạp của thuật toán là: O(t*8192)
  với t tối đa là 10^4 thì vừa đẹp

  code C++

  #include<bits/stdc++.h>
  #define ll long long
  using namespace std;
  vector<ll> a;
  void ham(ll i,ll t)
  {
      if(i>13)
      {
          if(t==0) return;
          a.push_back(t);
          return;
      }
      ham(i+1,t*10);
      ham(i+1,t*10+9);
      return ;
  }
  int main()
  {
      ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
      ham(1,0);
      sort(a.begin(),a.end());
      ll t;
      cin>>t;
      ll n;
      while(t>0)
      {
          t--;
          cin>>n;
          for(ll i=0;i<a.size();i++)
          {
              if(a[i]%n==0)
              {
                  cout<<a[i]<<endl;
                  break;
              }
          }
      }
  }
  

5 bình luận nữa