2008B

08年度-ACM-ICPC国内予選

2008B †

回答者：ほへい
所要時間：3時間
予選時：クリア/5ミス?

全部ファイルの送り間違いです。
ペナルティ加算しまくり。申し訳ない限りで…。
B問題だから強引にいっても大丈夫だろうと踏んで爆死した良い例。
今泉先生の解答例みるまでエラトステネスのふるいが使えることに気付きませんでした。
問題とコードを見ればわかると思うんで解説はパスします。

#include <iostream>
#include <fstream>
#include <vector>
#include <cmath>

const char *const fileNameIn("B_in.txt");
const char *const fileNameOut("B_out.txt");

std::ifstream f_in(fileNameIn);
std::ofstream f_out(fileNameOut);

std::vector<int> prime;

void searchPrime();
bool isGetuDo(int a);
void getAnswer(int searchNum);

int main()
{
    if( !f_in || !f_out)
    {
        std::cout << "ファイルが開けませんでした\n";
    }

    prime.push_back(6);
    prime.push_back(8);

    std::cout << "searchStart" << std::endl;
    searchPrime();
    std::cout << "end : " << prime.size() << std::endl;

    int searchNum;
    while(true)
    {
        f_in >> searchNum;
        if(searchNum == 1) break;

        getAnswer(searchNum);
    }

    f_in.close();
    f_out.close();
    return 0;
}

bool isGetuDo(int a) {  
    return (a % 7 == 1) || (a % 7 == 6);
}

void searchImpl(int i)
{           
    std::vector<int>::iterator iter = prime.begin();
    std::vector<int>::iterator endIter = prime.end();
            
    bool isPrime = true;

    int limit = (int)sqrt((double)i);
    for(; iter != endIter; ++iter)
    {
        if(limit < (*iter)) break;
        
        if((i % (*iter) == 0) ) 
        {
            isPrime = false;
            break;
        }
    }
    if(isPrime)  prime.push_back(i);
}

void searchPrime()
{
    int i = 2;
    while(true)
    {
        if((i * 7 - 1) <= 300000)   searchImpl(i * 7 - 1);
        if((i * 7 + 1) <= 300000)   searchImpl(i * 7 + 1);
        if((i * 7 + 1) >= 300000) break;
        i++;
    }
}

void getAnswer(int searchNum)
{
    f_out << searchNum << ':';
    std::vector<int>::iterator iter = prime.begin();
    std::vector<int>::iterator endIter = prime.end();

    for(; iter != endIter; ++iter)
    {
        if(searchNum % (*iter) == 0 && isGetuDo(searchNum / (*iter))) 
        {
            f_out << " " << (*iter);
        }
    }
    f_out << std::endl;
}