Sample Output
Case 1: 2
Case 2: 2
Case 3: 3
Case 4: 5
Case 5: 4
Case 6: 5
Case 7: 8
Case 8: 5
Case 9: 8
Case 10: 8
Case 11: 5
Case 12: 11
Case 13: 3
Case 14: 4
Case 15: 2
题解：把n分解，记下各个因子的个数，假设（a,b）满足LCM（a,b）==n，
则对于n的每种因子num[i],a,b中至少有一个数该种因子的个数为num[i];
另外一个则有k种情况，，还有一种情况是a=b,即两个数该种因子都为num[i].
所以，一种因子的情况为C(2,1)*num[i]+1.将每种因子的情况数相乘就是答案了。
#include<cstring>#include<cstdio>#include<iostream>#include<algorithm>#include<cmath>#include<vector>#define ll long long#define N 10000010using namespace std;ll n;vector<int>vec;bool _is[N];void init() {memset(_is,0,sizeof _is);_is[0]=_is[1]=1;for(int i=2; i<N; i++) {if(!_is[i]) {vec.push_back(i);for(int j=i+i; j<N; j+=i)_is[j]=1;}}}int main() {freopen("test.in","r",stdin);init();int t;int ca=1;cin>>t;while(t–) {scanf("%lld",&n);ll ans=1;int k;for(int i=0; i<vec.size(); i++) {if(n<vec[i])break;k=0;if(n%vec[i]==0) {while(n%vec[i]==0) {k++;n/=vec[i];}}if(k)ans*=(2*(k)+1);}if(n!=1)ans*=3;//最后一个因子printf("Case %d: %lld\n",ca++,(ans+1)/2);//由题意，答案要除以二}return 0;}
你曾经说，你曾经说。走在爱的旅途，我们的脚步多么轻松……
