首页 > 代码库 > XDOJ 1201: Dogs of Qwordance Senior Backend R&D Engineers
XDOJ 1201: Dogs of Qwordance Senior Backend R&D Engineers
XDOJ 1201: Dogs of Qwordance Senior Backend R&D Engineers
题目链接：http://acm.xidian.edu.cn/problem.php?id=1201
题目大意：已知长宽均为整数的矩形面积为$n$，现要在该矩形上划上水平和垂直间隔为相同整数的网格，问有多少种方案.
组合数
若将数$x$按素因数分解，可以得到$x=\prod_{i=0}^kp_i^{c_i}$，从而有$\tau(x)=\prod_{i=0}^k(c_i+1)$，其中$\tau(x)$为$x$的因子数.
由题意得到，方案数为$\sum_{d|n}\tau(d) \times \tau(n/d)=\prod_{i=0}^k(\sum_{j=0}^{c_i}(j+1)(c_i-j+1))$.
注意素因数分解时，需要预处理$\sqrt{n}$内的素数，使原本$O(\sqrt{n})$的分解复杂度降为$O(\pi(\sqrt{n}))$，即$O(\frac{\sqrt{n}}{lnn})$.
代码如下：
1 #include <iostream> 2 #define N 1000005 3 using namespace std; 4 typedef long long ll; 5 ll n,p[N],k,ans; 6 bool v[N]; 7 void prime(){ 8 v[1]=1; 9 for(ll i=2;i<N;++i){10 if(!v[i])p[k++]=i;11 for(ll j=0;j<k&&p[j]*i<N;++j){12 v[p[j]*i]=1;13 if(i%p[j]==0)break;14 }15 }16 }17 int main(void){18 std::ios::sync_with_stdio(false);19 prime();20 while(cin>>n){21 ans=1;22 for(int i=0;p[i]*p[i]<=n;++i)if(n%p[i]==0){23 ll tot=0,t=0;24 while(n%p[i]==0){25 tot++;26 n/=p[i];27 }28 for(ll j=0;j<=tot;++j)29 t+=(j+1)*(tot-j+1);30 ans*=t;31 }if(n!=1)ans*=4;32 cout<<ans<<"\n";33 }34 }
XDOJ 1201: Dogs of Qwordance Senior Backend R&D Engineers
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。