2008B の変更点

追加された行はこの色です。
削除された行はこの色です。
2008B へ行く。
2008B の差分を削除
[[08年度-ACM-ICPC国内予選]]

***2008B [#i0a53608]

回答者：[[ほへい]]&br;
所要時間：3時間&br;
予選時：クリア/5ミス?&br;
&br;
全部ファイルの送り間違いです。&br;
ペナルティ加算しまくり。申し訳ない限りで…。~
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;
 }