HDU 2421 一个数的因数与质因数个数的关系
题面:一个数字的因数的因数的个数的立方和
听起来有点绕
SRE实战 互联网时代守护先锋,助力企业售后服务体系运筹帷幄!一键直达领取阿里云限量特价优惠。就是对于一个数 找到它的所有因数 对于这些找到的每一个因数 再找到它们所有的因数个数 然后把这些个数的立方和相加
对于8来说 它有4个因数 1 2 4 8
1有1个因数
2有2个因数
4有3个因数
8有4个因数
所以答案为13+23+33+43=36
对于一般情况,我们这样分析:
首先,找到一个数字的所有因数是比较困难的,我们比较熟悉的方式对一个数进行质因数分解
对于一个数n来说,可以分解为n=ai*bj*ck*......的形式且这种形式是唯一的
然后n的因数个数是有多少个呢?对于n任意一个因数,都是由n的这些质因数相乘得到的
举个具体的例子
12=2*2*3=22*3
如何找到它的所有因数
对于2来说,我们可以不选2,选一个2,选两个2,对于3,可以不选3或者选一个3,不选的就乘1。有人会问这是啥意思?看完下面你就懂
1*1=1
2*1=2
22*1=4
1*3=3
2*3=6
22*3=12
大家应该可以看出规律了吧:对于n=ai*bj*ck*......的每一因数m,就a而言,m可能包含0个a,1个a,2个a,...i个a
就b而言,m可能包含0个b ... j个b
... ...
所以n共有(i+1)(j+1)(k+1)...个因数
下面就可以解这道题目了:
还是n=ai*bj*ck*......这个数
它的因数和因数的个数是
1 1
a 2
a2 3
a3 4
...
ai i+1
这部分的和就是13+23+33+...(i+1)3
下面继续,考虑上b
b 2
a*b 2*2
a2*b 2*3
...
b2 3
a*b2 3*2
...
算上这部分的,个数就是
[13+23+33+...(i+1)3][13+23+33+...(j+1)3]
以此类推
最后答案是
[13+23+33+...(i+1)3][13+23+33+...(j+1)3][13+23+33+...(k+1)3]...
然后三次方和可以直接用立方和公式求解,然后取模,就可以啦
#include<bits/stdc++.h> using namespace std; bool is_prime(long long x){ if(x==1) return false; if(x==2||x==3) return true; if(x%6!=1&&x%6!=5) return false; int s=sqrt(x); for(int i=5;i<=s;i+=6) if(x%i==0||x%(i+2)==0) return false; return true; } vector<long long> pfc(long long n){//快速质因数分解 vector <long long> st; long long i=0; if(n==1) { st.push_back(1); return st; } while(i<n) { if(is_prime(n)){ st.push_back(n); return st; } for(i=2;i<n;i++) { if(n%i==0) { st.push_back(i); n/=i; break; } } } st.push_back(n); return st; } long long readl(){ long long ans=0; char ch=getchar(); while(ch<='9'&&ch>='0') { ans=ans*10+ch-'0'; ch=getchar(); } return ans; } vector <long long> getsize(long long n){ vector <long long> st=pfc(n); long long tt=1; vector <long long> v; for(long long i=1;i<st.size();i++) { if(st[i]!=st[i-1]) { v.push_back(tt); tt=0; } tt++; } v.push_back(tt); return v; } int main() { long long A,B; int cas=1; while(true) { A=readl(); B=readl(); if(!(A&&B)) break; if(A==1) { printf("Case %d: %lld\n",cas++,1); continue ; } vector <long long> v=getsize(A); for(long long i=0;i<v.size();i++) v[i]=((v[i]%10007)*(B%10007))%10007; long long ans=1; for(long long i=0;i<v.size();i++) { v[i]=(v[i]+1)%10007; ans*=((v[i]*(v[i]+1)/2)%10007)*((v[i]*(v[i]+1)/2)%10007); ans=ans%10007; } printf("Case %d: %lld\n",cas++,ans); } }
