整数分解算法

#include<stdio.h> #include<math.h> struct DP { int num; int sum; } d[50000]= {0}; int max=0; void qsort(int low,int high,struct DP key[]) { int i=low,j=high; struct DP tag=key[i]; if(i<j) { do { while(tag.num<key[j].num && i<j) j--; if(i<j) { key[i]=key[j]; i++; while(tag.num>=key[i].num && i<j) i++; if(i<j) { key[j]=key[i]; j--; } } } while(i<j); key[i]=tag; qsort(low,j-1,key); qsort(i+1,high,key); } } int dfs(int left) { int i,p; int l,r,m; int count=0; l=0; r=max; while(l<=r) { m=(l+r)>>1; if(d[m].num<left) l=m+1; else r=m-1; } p=l; if(d[p].sum) return d[p].sum; for(i=1; i<=d[i].num; i++) { if(left%d[i].num==0) count+=dfs(left/d[i].num); } d[p].sum=count; return count; } int main(void) { int i,j,tmp; int n; scanf("%d",&n); tmp=sqrt(n); for(i=1; i<=tmp; i++) { if(n%i==0) { d[max].num=i; max++; d[max].num=n/i; max++; } } max--; qsort(0,max,d); d[0].sum=1; printf("%d\n",dfs(n)); return 0; }