筛选法

记录点滴。
  1 /*
  2 2015.6    HT
  3 ACM Work_6
  4 
  5 */
  6 #include <iostream>
  7 #include <cstdio>
  8 using namespace std;
  9 
 10 
 11 /*
 12 七夕节
 13 
 14 */
 15 //int main()
 16 //{
 17 //    int T, a, i;
 18 //    cin >> T;
 19 //    while (T--)
 20 //    {
 21 //        cin >> a;
 22 //        int sum = 1;
 23 //        int k = (int)sqrt((double)a);
 24 //        for (i = 2; i <= k; i++)
 25 //        {
 26 //            int t;
 27 //            if (a%i == 0)
 28 //            {
 29 //                sum += i;
 30 //                t = a / i;
 31 //                if (t != i)
 32 //                    sum += t;
 33 //            }
 34 //        }
 35 //        cout << sum << endl;
 36 //    }
 37 //    return 0;
 38 //}
 39 
 40 
 41 
 42 /*
 43 找新朋友
 44 和N有大于1的公约数都是新朋友
 45 
 46 用筛选法, 因为num如果能整除 i  ,i > 1, 那么对 i 的倍数, 肯定有大于1的公约数
 47 */
 48 //int p[40000];
 49 //int euler(int num)
 50 //{
 51 //    memset(p, 0, sizeof (p));
 52 //    int cnt = 0;
 53 //    for (int i = 2; i <= num / 2; ++i)
 54 //    {
 55 //        if (num % i == 0 && p[i] == 0)
 56 //        {
 57 //            for (int j = i; j < num; j += i)
 58 //            {
 59 //                if (p[j] == 0)
 60 //                    cnt++;
 61 //                p[j] = 1;
 62 //            }
 63 //        }
 64 //    }
 65 //    return num - cnt - 1;
 66 //}
 67 //
 68 //int main()
 69 //{
 70 //    int T;
 71 //    cin >> T;
 72 //    while (T--)
 73 //    {
 74 //        int num;
 75 //        cin >> num;
 76 //        cout << euler(num) << endl;
 77 //    }
 78 //    return 0;
 79 //}
 80 
 81 
 82 
 83 /*
 84 平方和与立方和
 85 
 86 */
 87 //int main()
 88 //{
 89 //    int n, m, sum1, sum2, i, t;
 90 //    while (scanf_s("%d%d", &n, &m) && n && m)
 91 //    {
 92 //        if (n>m)
 93 //        {
 94 //            t = n;
 95 //            n = m;
 96 //            m = t;
 97 //        }
 98 //        sum1 = 0;
 99 //        sum2 = 0;
100 //        for (i = n; i <= m; i++)
101 //        {
102 //            if (i % 2 == 0)
103 //                sum1 += i*i;
104 //            else
105 //                sum2 += i*i*i;
106 //        }
107 //        printf_s("%d %d
", sum1, sum2);
108 //    }
109 //    return 0;
110 //}
111 
112 
113 
114 /*
115 Hamming Problem
116 三个质数p1,p2,p3，因子只包含他们的数构成连续的一列数，问第K个数是什么?
117 
118 */
119 __int64 h[10000];
120 __int64 min(__int64 a, __int64 b)
121 {
122     return a<b ? a : b;
123 }
124 
125 int main()
126 {
127     int a, b, c, i, k;
128     // LONGLONG
129     __int64 p, q, r;
130     while (scanf_s("%I64d%I64d%I64d%d", &p, &q, &r, &k) != EOF)
131     {
132         a = b = c = 1;
133         h[1] = 1;
134         for (i = 2; i <= k + 1; i++)
135         {
136             h[i] = min(p * h[a], min(q * h[b], r * h[c]));
137             if (h[i] == p * h[a])
138                 a++;
139             if (h[i] == q * h[b]) 
140                 b++;
141             if (h[i] == r * h[c])
142                 c++;
143         }
144         printf_s("%I64d
", h[k + 1]);
145     }
146     return 0;
147 }