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}$，从而有$ au(x)=prod_{i=0}^k(c_i+1)$，其中$ au(x)$为$x$的因子数.

由题意得到，方案数为$sum_{d|n} au(d) imes au(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})$.

总复杂度为$O(n+T(frac{sqrt{n}}{lnn}+lg^2n))$

代码如下：

 1 #include <cstdio>
 2 #define N 1000005
 3 using namespace std;
 4 typedef long long ll;
 5 ll n,p[N],k,ans,a[N],d;
 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     prime();
19     while(~scanf("%lld",&n)){
20         ans=1;d=0;
21         for(int i=0;p[i]*p[i]<=n;++i)if(n%p[i]==0){
22             ll tot=0;
23             while(n%p[i]==0){
24                 tot++;
25                 n/=p[i];
26             }
27             a[d++]=tot;
28         }if(n!=1)ans*=4;
29         for(ll i=0;i<d;++i){
30             ll t=0;
31             for(ll j=0;j<=a[i];++j)
32                 t+=(j+1)*(a[i]-j+1);
33             ans*=t;
34         }
35         printf("%lld
",ans);
36     }
37 }