hdu1215 七夕节---因子和

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=1215

题目大意：

求N的因子和（不包括N本身）

解题思路：

模板传送门

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<stack>

 #include<map>

 #include<sstream>

 #define Mem(a, b) memset(a, b, sizeof(a))

 using namespace std;

 typedef long long ll;

 const int INF = 1e9 + ;

 const int maxn = +;

 int prime[maxn];

 bool is_prime[maxn];

 int sieve(int n)//返回n以内素数的个数

 {

     int p = ;

     for(int i = ; i <= n; i++)is_prime[i] = ;

     is_prime[] = is_prime[] = ;

     for(ll i = ; i <= n; i++)

     {

         if(is_prime[i])

         {

             prime[p++] = i;

             for(ll j = i * i; j <= n; j += i)is_prime[j] = ;//这里涉及i*i,必须使用long long

         }

     }

     return p;

 }

 ll Divisors_num(ll n, int tot)//素数总数

 {

     ll ans = ;

     for(int i = ; i < tot && prime[i] * prime[i] <= n; i++)

     {

         if(n % prime[i] == )

         {

             int cnt = ;

             while(n % prime[i] == )

             {

                 cnt++;

                 n /= prime[i];

             }

             ans *= (cnt + );

         }

     }

     if(n > )ans *= ;

     return ans;

 }

 ll pow(ll a, ll b)

 {

     ll ans = ;

     while(b)

     {

         if(b & )ans = ans * a;

         a *= a;

         b /= ;

     }

     return ans;

 }

 ll Divisors_sum(ll n, int tot)

 {

     ll ans = ;

     for(int i = ; i < tot && prime[i] * prime[i] <= n; i++)

     {

         if(n % prime[i] == )

         {

             int cnt = ;

             while(n % prime[i] == )

             {

                 cnt++;

                 n /= prime[i];

             }

             ans = (pow(prime[i], cnt + ) - ) / (prime[i] - ) * ans;

         }

     }

     if(n > )ans *= (n + );

     return ans;

 }

 int main()

 {

     int T, cases = ;

     int tot = sieve();

     cin >> T;

     while(T--)

     {

         ll n;

         scanf("%lld", &n);

         printf("%lld\n", Divisors_sum(n, tot) - n);

     }

     return ;

 }