1173: 这是物理学的奇迹!!
题目描述
goagain在做物理电学实验时需要一个2Ω的电阻,但是他发现他的实验台上只剩下了3Ω,4Ω,5Ω,6Ω的电阻若干,于是goagain把两个4Ω的电阻并联起来,发现效果也不错,于是他惊呼,这是物理学的奇迹!!
实验结束之后goagain思考了一下,其实用1个3Ω的电阻和一个6Ω的电阻并联一下也是不错的,但是似乎没有其他的方法可以并联两个电阻得到等效的2Ω电阻了.
goagain就想啊,如果我需要一个k Ω的电阻,但是我的手头上只有k+1 Ω,k+2 Ω,.....,一直到正无穷的整数Ω电阻,那么我有多少种办法把他们其中的两个并联起来,得到一个k Ω的电阻呢?
goagain仔细想了想,终于发现自己的智力不足以解决这样的问题,于是他不得不感叹:这真是物理学的奇迹!
输入要求
有多组测试数据,每组数据包含一个正整数k(k<2^16),处理到文件结束
输出要求
对于每组测试数据,输出一个正整数,代表方法的总数
假如输入
应当输出
提示
1/2=1/3+1/6=1/4+1/4
1/3=1/4+1/12=1/6+1/6
由公式 1/k=1/a+1/b ，转换成 1/k=1/(c+k)+1/(d+k)。进行化简。得到这样的一条式子: k*k = c*d; 另N=k*k。 则N=c*d。很显然的，题目转换成了求能整除N的数的个数。
由因式分解可知。
设pi为N的因子。有 N=p1^a * p2^b * p3^c ..... 等。 可以知道。p1可以取0到a个，p2可以取0到b的个,p3可以取0到c个。因此可以得出这样的式子。 能整除N的数的个数=(a+1)*(b+1)*(c+1)*....
因此。我们只需快速的对N进行因式分解，即可快速的算出答案，不过还得留意N是n*n的情况，需要多加一次。
最后记得将答案除以2.因为ab重复了。 当n=1时。是个特殊情况
筛法求素数的模板getprm()快速获得素数
求 k*k分解时有个小小的优化。。就是可以求出每个k的a,b,c最后算k*k时，是2a,2b,2c。这个优化还是比较明显的。从1100MS掉到了220MS
当然因为k < 2^16次。我们可以直接设计个方法用数组记录答案。理论上存在的。不过设计起来比较麻烦。
/*
* @user ipqhjjybj
* @Time
* @data 20130701
*/
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <ctime> #include <iostream>
#include <cmath>
#include <algorithm>
#include <numeric>
#include <utility> #include <cstring>
#include <vector>
#include <stack>
#include <queue>
#include <map>
#include <string>
using namespace std; #define inf 0x3f3f3f3f
#define MAXN 800000 #define clr(x,k) memset((x),(k),sizeof(x))
#define clrn(x,k) memset((x),(k),(n+1)*sizeof(int))
#define cpy(x,k) memcpy((x),(k),sizeof(x))
#define Base 10000 typedef vector<int> vi; #define foreach(it,c) for(vi::iterator it = (c).begin();it != (c).end();++it) #define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
bool is[MAXN];int prm[MAXN];
int k;
int getprm(int n){
int i,j,k;
for(i=0;i<n;i++) is[i]=true;
is[0]=is[1]=false;
k=0;
for(i=2;i<n;i++){
if(is[i]){
prm[k++]=i;
for(j=i+i;j<n;j+=i)
is[j]=false;
}
}
return k;
} int fenjie(int n){
int i,zn,j,ans=1;
for(i = 0,zn=prm[i];prm[i]<=n;++i,zn = prm[i]){
if(n%zn==0){
j=1;
n/=zn;
while(!(n%zn)){
n/=zn;j++;
}
ans*=(j+j+1); //我们分解的可是n*n哦。。所以是2*j
} }
return ans+1; //当n*n情况时！
}
int main(){
long long n;
k=getprm(MAXN); while(scanf("%lld",&n)!=EOF){
if(n==1)printf("1\n");
else printf("%d\n",fenjie(n)>>1);
}
return 0;
}