链接:
http://www.codeforces.com/problemset/problem/236/B
题目:
分析与总结:
裸的求因子个数,数据比较水可以暴力过,但是只要给个100 100 100, 就会因TLE被别人hack掉的。
对于我这种数学弱逼,打CF时只能临时百度个更高效的的方法了...
条件:给定任意一个一个正整数N
要求:求其因子的个数
首先给出结论:对于任意的整型N,分解质因数得到N= P1^x1 * P2^x2* …… * Pn^xn;
则N的因子个数M为 M=(x1+1) * (x2+1) * …… *(xn+1);
证明过程:
首先 举个例子吧
24 = 2^3 * 3^1;
其质因子有:为2和3
那么对于2 有0 1 2 3四种指数选择,对于3 有0 1两种指数选择
所以 就是4 * 2 = 8 个因子个数
如果还是不懂,那么我们就列举出来吧
2 3
2^0*3^0=1
2^1*3^0=2
2^2*3^0=4
2^3*3^0=8
结果很清晰了吧??其实这里用到了数学的排列组合的知识
也就是说每一个质因子的不同指数幂与其它质因子相乘,得到的结果一定不会重复
因此能够将所有的因子都列举出来。
所以N的因子数M,我们可以用M=(x1+1) * (x2+1) * …… *(xn+1)表示
参考资料:http://blog.sina.com.cn/s/blog_818d3d9301017436.html
代码:
#include<iostream> #include<cstdio> #include<cstring> using namespace std; const int MOD = 1073741824; const int Maxn = 1000005; int w[6600]; int ans[Maxn], n; // 判断是否是质数 bool isPrime(int n) { if(n<=1)return false; if(n==2)return true; if(n!=2&&n%2==0)return false; int i; for(i=3;i*i<=n;i+=2) if(n%i==0)return false; return true; } // 计算因子个数 int count(int n){ if(ans[n]!=-1)return ans[n]; int a=n, i=0, sum=1; while(a!=1 && i<n){ int cnt=0; while(a%w[i]==0){ ++cnt; a /= w[i]; } if(cnt) sum*=(1+cnt); ++i; } ans[n] = sum; return ans[n]; } int main(){ int a,b,c; n=0; for(int i=1; i<(1<<16); i++) if(isPrime(i)) w[n++]=i; memset(ans, -1, sizeof(ans)); while(~scanf("%d%d%d",&a,&b,&c)){ int sum=0; for(int i=1; i<=a; ++i) for(int j=1; j<=b; ++j) for(int k=1; k<=c; ++k){ sum += count(i*j*k); if(sum > MOD) sum %= MOD; } printf("%d\n",sum); } return 0; }
—— 生命的意义,在于赋予它意义。
原创 http://blog.csdn.net/shuangde800 , By D_Double (转载请标明)