七夕节

Problem Description

七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"
人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下:



数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
你想知道你的另一半吗?

 

Input

输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

 

Output

对于每组测试数据,请输出一个代表输入数据N的另一半的编号.

 

Sample Input

 

Sample Output

 

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <cmath>
 4 #include <vector>
 5 using namespace std;
 6 
 7 const int N = 500010;
 8 
 9 struct Factor {
10     int p, e;
11     Factor(int p = 0, int e = 0) :p(p), e(e) {}
12 };
13 
14 bool not_prime[N] = { 1,1,0 };
15 vector<int> P;
16 
17 void E_prime() {
18     int m = (int)sqrt(N + 0.5);
19     for (int i = 2; i <= m; ++i)if (!not_prime[i])
20         for (int j = i*i; j < N; j += i)
21             not_prime[j] = true;
22     for (int i = 2; i < N; ++i)if (!not_prime[i])P.push_back(i);
23 }
24 
25 void Divided_by_Prime(int n, vector<Factor>& ve) {
26     double f = sqrt(n);
27     int t = 0;
28     for (int i = 0; P[i] <= f&&i < N; ++i)
29         if (n%P[i] == 0) {
30             ve.push_back(Factor(P[i], 1));
31             ++t, n /= P[i];
32             while (n%P[i] == 0) { n /= P[i]; ++ve[t - 1].e; }
33         }
34     if (!not_prime[n])ve.push_back(Factor(n, 1));
35 }
36 
37 int main() {
38     E_prime();
39     int t, n;
40     scanf("%d", &t);
41     while (t--) {
42         scanf("%d", &n);
43         vector<Factor> ve;
44         Divided_by_Prime(n, ve);
45         int sum = 1;
46         for (int i = 0; i < (int)ve.size(); ++i)
47             sum *= ((int)(pow(ve[i].p, ve[i].e + 1) + 1e-3) - 1) / (ve[i].p - 1);
48         printf("%d\n", sum - n);
49     }
50 }