【ECJTU_ACM 11级队员2012年暑假训练赛（8） D Distinct Primes】

B题要套一个数论的模版，注意m=1！！ C题可以二分匹配，把行列看作点; 不能开百度，开谷歌搜题解，再次强调！一经发现，取消成绩！

  1 // Project name : D ( Distinct Primes ) 
  2 // File name    : main.cpp
  3 // Author       : iCoding
  4 // E-mail       : honi.linux@gmail.com
  5 // Date & Time  : Fri Aug 10 14:04:18 2012
  6 
  7 
  8 #include <iostream>
  9 #include <stdio.h>
 10 #include <string>
 11 #include <cmath>
 12 #include <algorithm>
 13 using namespace std;
 14 
 15 /*************************************************************************************/
 16 /* data */
 17 
 18 #ifndef MAXN
 19 #define MAXN 2000
 20 #endif
 21 
 22 bool iIsPrime[MAXN*MAXN];
 23 
 24 int iMap[MAXN];
 25 int iTop;
 26 /*************************************************************************************/
 27 /* procedure */
 28 
 29 void debug()
 30 {
 31     cout << "--" << endl;
 32 }
 33 
 34 bool iIsLuckyNumber(int iNum)
 35 {
 36     int count = 0;
 37     int i = 2;
 38     while (iNum > 1)
 39     {
 40         if (iNum % i == 0)
 41         {
 42             count++;
 43             while (iNum % i == 0)
 44             {
 45                 iNum /= i;
 46             }
 47         }
 48         else
 49         {
 50             i++;
 51             while (!iIsPrime[i])
 52             {
 53                 i++;
 54                 //cout << i << endl;
 55             }
 56         }
 57     }
 58     return count >= 3 ? true : false;
 59 }
 60 
 61 void iMakeMap()
 62 {
 63     iTop = 0;
 64     int iNum = 30;
 65     while (iTop <= MAXN)
 66     {
 67         if (iIsLuckyNumber(iNum))
 68         {
 69             iTop++;
 70             iMap[iTop] = iNum;
 71         }
 72         iNum++;
 73     }
 74 }
 75 
 76 void iMakePrime()
 77 {
 78     for (int i = 0; i < MAXN * MAXN; i++)
 79     {
 80         iIsPrime[i] = true;
 81     }
 82     iIsPrime[0] = false;
 83     iIsPrime[1] = false;
 84 
 85     for (int i = 2; i * i < MAXN; i++)
 86     {
 87         if (iIsPrime[i])
 88         {
 89             for (int j = i * i; j < MAXN; j += i)
 90             {
 91                 iIsPrime[j] = false;
 92             }
 93         }
 94     }
 95 }
 96 
 97 void iShowMap()
 98 {
 99     for (int i = 1; i <= MAXN; i++)
100     {
101         cout << iMap[i] << endl;
102     }
103 }
104 /*************************************************************************************/
105 /* main */
106 int main()
107 {
108     iMakePrime();
109     iMakeMap();
110     //iShowMap();
111 
112     int iT;
113     cin >> iT;
114     while (iT--)
115     {
116         int n;
117         cin >> n;
118         cout << iMap[n] << endl;
119     }
120     return 0;
121 }
122 
123 // end 
124 // Code by Sublime text 2
125 // iCoding@CodeLab

【ECJTU_ACM 11级队员2012年暑假训练赛（8） D Distinct Primes】

ACM International Collegiate Programming Contest, Asia-Amritapuri Site, 2011

Problem E: Distinct Primes

Input (STDIN):

Output (STDOUT):

Constraints:

Sample Input:

Sample Output: