要求
[frac{1}{x} +frac{1}{y} = frac{1}{n} \
]
x,y,n都是正整数，且x<=y的(x,y)解数
[egin{align}
frac{1}{x} +frac{1}{y} &= frac{1}{n} \
n(x+y) &=xy \
end{align}
]
显然x,y均大于n
设 x=n+a,y=n+b
[n^2=ab
]
所以答案就是(a,b)的对数
设P为n的约数个数，因为x<=y,所以答案为(p+1)/1
若p为偶数，则答案为p/2，否则为(p+1)/2,所以就是(p+1)/2
n<=1e9,但是n最大质因子<=1e5
那么根据算术基本定理，n^2的可以从n来计算
int v[100007], prime[100007], cnt;
inline void Euler_Sieve(int mx) {
rep(i, 2, mx) {
if(!v[i]) {
v[i] = i;
prime[++cnt] = i;
}
rep(j, 1, cnt) {
if(prime[j] > v[i] || 1ll * prime[j]*i > mx) break;
v[i * prime[j]] = prime[j];
}
}
}
inline lxl calc(lxl n) {
lxl ans(1);
rep(i, 1, cnt) {
lxl c(0);
while(n % prime[i]==0) {
n /= prime[i];
++c;
}
ans *= (2 * c + 1);
}
if(n > 1) ans = (ans << 1) + ans;
return ans;
}
int main() {
lxl T,n;
cin>>T;
Euler_Sieve(100000);
rep(p, 1, T) {
cin>>n;
lxl res = calc(n);
printf("Scenario #%d:
%lld
", p, (res + 1) / 2);
}
return 0;
}