AOJの問題です。

フォーラム(掲示板)ルール
フォーラム(掲示板)ルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
hogged
記事: 17
登録日時: 9年前

AOJの問題です。

#1

投稿記事 by hogged » 9年前

AOJの問題(http://judge.u-aizu.ac.jp/onlinejudge/d ... 54&lang=jp)を解いているのですが、テストケースなどでは正確に答えが出ているのですが、WAになってしまいます。
考え方は、約数であるものをまず見つけて、その後、素数であるかを判定しています。そして見つかったものをvに入れて、最後に出力しています。
色々なケースで試してみたのですが、WAになる原因がわからないので、教えてくれると助かります。お願いします。

コード:

#include <iostream>
#include <string>
#include <algorithm>
#include <functional>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
using namespace std;
typedef long long ll;
typedef pair<int,int> pint;
typedef vector<int> vint;
typedef vector<pint> vpint;
#define mp make_pair
#define fi first
#define se second
#define all(v) (v).begin(),(v).end()
#define rep(i,n) for(int i=0;i<(n);i++)
#define reps(i,f,n) for(int i=(f);i<(n);i++)

int cnt;
vector<int> v;//約数であり素数でもある数を入れていく


//答えを出力
void print(int num){
	printf("%d:", num);
	for (int i = 0; i < v.size(); ++i){
		printf(" %d", v[i]);
	}
	printf("\n");
	return;
}


//その約数が素数かどうかを確かめる
void check(int yakusu){
	for (int i = 6; i < yakusu; i += 7){
		if (yakusu % i == 0) return;
	}
	for (int i = 8; i < yakusu; i += 7){
		if (yakusu % i == 0) return;
	}

	v.push_back(yakusu);//素数であったので入れる
	return;
}

void slove(int num){
	//約数であるかを探し、それが素数であるかをcheck()関数で素数かどうかを判定へ
	for (int i = 6; i<= num; i += 7){
		if (num % i == 0) check(i);
		if (num % (i + 2) == 0) check(i + 2);
	}
	return;
}

int main(void){
	int n;
	rep(i, 1000){
		scanf("%d", &n);
		if(n == 1) break;
		slove(n);
		print(n);
		v.clear();//vがグローバル変数に入っているので、これで削除しないと変な挙動に
	}	

	return 0;
}

アバター
みけCAT
記事: 6734
登録日時: 14年前
住所: 千葉県
連絡を取る:

Re: AOJの問題です。

#2

投稿記事 by みけCAT » 9年前

処理の内容はチェックしていないですが少なくとも、テストケースは1000行を超えているのにmain関数で1000回しか処理をしないようにしているのがダメですね。
余計な条件を入れず、(nに1が入るまでの)無限ループにしてみてください。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

hogged
記事: 17
登録日時: 9年前

Re: AOJの問題です。

#3

投稿記事 by hogged » 9年前

みけCAT さんが書きました:処理の内容はチェックしていないですが少なくとも、テストケースは1000行を超えているのにmain関数で1000回しか処理をしないようにしているのがダメですね。
余計な条件を入れず、(nに1が入るまでの)無限ループにしてみてください。
無限ループにしたら通りました。本当にありがとうございました。またお願いします。

閉鎖

“C言語何でも質問掲示板” へ戻る