結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー SakaTaku
提出日時 2020-09-03 00:36:49
言語 C++14
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 5 ms / 5,000 ms
コード長 1,449 bytes
コンパイル時間 1,602 ms
コンパイル使用メモリ 173,000 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 16:58:47
合計ジャッジ時間 2,510 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function 'int main()':
main.cpp:76:9: warning: 'ans' may be used uninitialized [-Wmaybe-uninitialized]
   76 |   cout<<ans<<endl;
      |         ^~~
main.cpp:57:15: note: 'ans' was declared here
   57 |   int l=0,r=0,ans,Max=0;
      |               ^~~

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0; i < n; ++i)
using ll = long long;
using P = pair<int,int>;
int K,N;
struct Sieve {
  int n;
  vector<int> f, primes;
  Sieve(int n=1):n(n), f(n+1) {
    f[0] = f[1] = -1;
    for (ll i = 2; i <= n; ++i) {
      if (f[i]) continue;
      if(i>=K)primes.push_back(i);
      f[i] = i;
      for (ll j = i*i; j <= n; j += i) {
        if (!f[j]) f[j] = i;
      }
    }
  }
  bool isPrime(int x) { return f[x] == x;}
  vector<int> factorList(int x) {
    vector<int> res;
    while (x != 1) {
      res.push_back(f[x]);
      x /= f[x];
    }
    return res;
  }
  vector<P> factor(int x) {
    vector<int> fl = factorList(x);
    if (fl.size() == 0) return {};
    vector<P> res(1, P(fl[0], 0));
    for (int p : fl) {
      if (res.back().first == p) {
        res.back().second++;
      } else {
        res.emplace_back(p, 1);
      }
    }
    return res;
  }
};
int h(int x){
  if(x<10)return x;
  int y=0;
  while(x!=0){
    y+=x%10;
    x/=10;
  }
  return h(y);
}
bool check[10]; 
int main() {
  cin>>K>>N;
  Sieve prime(N);
  int l=0,r=0,ans,Max=0;
  vector<int>P=prime.primes;
  rep(i,P.size()){
    P[i]=h(P[i]);
  }
  while(r<P.size()){
    int now=P[r];
    while(check[now]){
      int pre=P[l];
      check[pre]=false;
      l++;
    }
    check[now]=true;
    r++;
    if(Max<=(r-l)){
      Max=r-l;
      ans=prime.primes[l];
    }
  }
  cout<<ans<<endl;
}
0