Freddy practices various kinds of alternative medicine, such as homeopathy. This practice is based on the belief that successively diluting some substances in water or alcohol while shaking them thoroughly produces remedies for many diseases.
This year, Freddy’s vegetables appear to have caught some disease and he decided to experiment a little bit and investigate whether homeopathy works for vegetables too. As Freddy is also a big fan of mathematics, he does not strictly insist that the substances have small concentrations, but he instead requires the concentrations to be reciprocals of integers (1/n). In experiments, some of the vegetables really got much better.
Seeing Freddy’s successes, a fellow gardener also wants to try one of these potions and asks for a flask. Freddy has one flask of the potion in concentration 1/n and does not want to give it all out. Your task is to find out in how many ways the potion can be split into two flasks and diluted so that the resulting potions both have the same volume as the original one and the resulting concentrations also are reciprocals of integers — we do not want to end up with useless fluid, do we?
Input
Each line of the input describes one test case. The line contains the expression “1/n” representing the original concentration. You are guaranteed that 1≤n≤10000. There are no spaces on the line.
Output
For each test case, output a single line with the total number of distinct pairs {x,y}
of positive integers satisfying 1/x+1/y=1/n. Pairs differing only in the order of the two numbers are not considered different.
| Sample Input 1 | Sample Output 1 |
|---|---|
1/2 |
2 |
感谢大佬的思路：http://blog.csdn.net/HelloWorld10086/article/details/44022071?locationNum=8&fps=1
//Asimple
#include <bits/stdc++.h>
#define CLS(a, v) memset(a, v, sizeof(a))
using namespace std;
typedef long long ll;
const int maxn = 10000+5;
ll n, m, s, res, ans, len, T, k, num;
int pr[maxn];
char str[maxn];
int a[maxn] = {0}; void get_pr(){
len = 0;
for(int i=2; i<maxn; i++) {
if( a[i]==0 ) {
pr[len++] = i;
int j = i;
while( j < maxn ) {
a[j] = 1;
j += i;
}
}
}
} void input() {
get_pr();
while( cin >> str ){
n = atoi(str+2);
res = 0;
CLS(a, 0);
for(int i=0; i<len && n>1; i++) {
if( n%pr[i]==0 ) {
while( n%pr[i]==0 ) {
a[res]++;
n /= pr[i];
}
res ++;
}
}
ans = 1;
for(int i=0; i<res; i++) {
ans *= (a[i]*2+1);
}
cout << (ans+1)/2 << endl;
}
} int main(){
input();
return 0;
}
数论菜鸟瑟瑟发抖。