Sherlock and Divisors

题目大意: 给定一个数N，求N的因子中能被2整除的个数。
算法: 循环1_{N，找出每个因子看是否能被整除，复杂度O(N)，超时！想到若a为因子，则N/a也是因子，所以循环1}sqrt(N)即可，注意当ii=N时不要重复加。
还有个方法，不过至少是O(N/2)，对于偶数N=2K，肯定有个因子K，假设K=p₁^e₁p₂^e₂...p_m^e_m，则N的因子中能被2整除的个数=K因子的排列组合=(e₁+1)(e₂+1)...*(e_m+1)。 +1是因为因子可以没有。
反思:思考再仔细些，尤其rainy case。
代码:

#include <bits/stdc++.h>
using namespace std;

int solve(int n) {
    int ret = 1;
    int p, e;
    if(n%2==0) {
        n /= 2;
        p = 2;
        while(p<=n) {
            if(p*p>n) p = n;
            e = 0;
            while(n%p==0) {
                ++e;
                n/=p;
            }
            ret *= e+1;
            ++p;
        }
    }
    return ret;

}
int main()
{
    int t, n;
    cin>>t;
    while(t--) {
        cin >> n;
        if(n%2) {
            cout << 0 << endl;
           continue;
        }
        int cnt = 0;
        int i;
        for(i=1; i*i<n; i++) {
            if(n%i==0) {
                if(i%2==0) ++cnt;
                if((n/i)%2==0) ++cnt;
            }
        }
        if(i*i==n&&i%2==0) ++cnt;
        cout << cnt << endl;
        //cout << solve(n) << endl;
    }
    return 0;
}