結果

問題 No.6 使いものにならないハッシュ
コンテスト
ユーザー FF256grhy
提出日時 2015-05-11 11:37:30
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 3 ms / 5,000 ms
コード長 1,119 bytes
コンパイル時間 134 ms
コンパイル使用メモリ 23,168 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-09-16 16:26:43
合計ジャッジ時間 1,062 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge6
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 32
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:14:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   14 |         scanf("%d%d", &m, &n);
      |         ~~~~~^~~~~~~~~~~~~~~~
main.cpp: In function ‘int search()’:
main.cpp:54:16: warning: ‘max_p’ may be used uninitialized in this function [-Wmaybe-uninitialized]
   54 |         return max_p;
      |                ^~~~~

ソースコード

diff # 

#include <stdio.h>

#define MAX 200000

void make_prime_list();
int search();
//int hash(int);

int m, n;
int table[MAX + 1]; // 0, 1番目は無視
int prime[MAX], p_cnt;

int main(void) {
	scanf("%d%d", &m, &n);
	make_prime_list();
	printf("%d\n", search());
	return 0;
}

void make_prime_list() {
	int i;
	for(i = 2; i <= n; i++) {
		if(table[i] == 0) { // 0のときにiは素数
			if(m <= i) {
				prime[p_cnt] = i;
				p_cnt++;
			}
			int multi = 2 * i;
			while(multi <= MAX) {
				table[multi] = 1;
				multi += i;
			}
		}
	}
	return;
}

int search() {
	int memo[9], max_l = 0, max_p;
	int i, j;
	for(i = p_cnt - 1; 0 <= i; i--) {
		for(j = 0; j < 9; j++) { memo[j] = 0; }
		j = i;
		while(j < p_cnt) {
			if( memo[ prime[j] % 9 ] ) { break; }
			memo[ prime[j] % 9 ]++;
			j++;
		}
		if(max_l < j - i) {
			max_l = j - i;
			max_p = prime[i];
		}
	}
	return max_p;
}

/* よく考えたらいらなかったやつ (hash(x) は x%9 と同一視できる(0を9とみなせばよい))
int hash(int x) {
	if(x < 10) { return x; }
	int sum = 0;
	while(x) {
		sum += x % 10;
		x /= 10;
	}
	return hash(sum);
}
*/
0