首先面对此题,最不该做的就是暴搜. U no it.
于是我们想到桶!
首先质因数分解(2,3,5,7), 如果n>1直接output -1.
然后我们就要把桶里面的数的个数压缩.
8=2*2*2 当然首当其冲.
然后是 9=3*3
然后是 6=2*3
然后是 4=2*2
这么做是对的, 不过一直感觉说不太明白, Wittgenstein告诉我们: 沉默.
然后就可以提交了.
如果你真的照上面做了, 而且确保没错, 那么恭喜你, WA#3.
不要重做. 我们只是漏掉了两个神级整数:
0 -> 10
1 -> 1
这样就AC了.
#include<iostream> using namespace std; int n; int T[10]; int main() { int i,j,k; scanf("%d",&n); if(n==0) { printf("10/n"); return 0; } if(n==1) { printf("1/n"); return 0; } while(!(n%2)) { n/=2; T[2]++; } while(!(n%3)) { n/=3; T[3]++; } while(!(n%5)) { n/=5; T[5]++; } while(!(n%7)) { n/=7; T[7]++; } if(n!=1) { printf("-1/n"); return 0; } while(T[2]>=3) { T[8]++; T[2]-=3; } while(T[3]>=2) { T[9]++; T[3]-=2; } while(T[2]>0&&T[3]>0) { T[2]--; T[3]--; T[6]++; } while(T[2]>=2) { T[2]-=2; T[4]+=1; } for(i=2;i<10;i++) for(j=1;j<=T[i];j++) printf("%d",i); printf("/n"); return 0; }
