[PAT-B] 1096 Consecutive Factors

cpcs

1096 Consecutive Factors

给定一个n，求n最长有多少个连续自然数的乘积一直可被n整除。

枚举…… 只要循环到sqrt(n)即可。

1. #include <cstdio>
   
2. #include <cstring>
   
3. #include <string>
   
4. using namespace std;
   
5. 
   
6. int getLen(int n, int x) {
   
7. int len;
   
8.         for (len = 0; n % (x + len) == 0; n /= (x + len++))
   
9.         ;
   
10.         return len;
    
11. }
    
12.        
    
13. int main() {
    
14. int n;
    
15.         scanf("%d",&n);
    
16.         int len = 0;
    
17.         int start = 0;
    
18.         for (int i = 2; n / i >= i; ++i) {
    
19.                 int may = getLen(n, i);
    
20.                 if (may > len) {
    
21.                         start = i;
    
22.                         len = may;
    
23.                 }
    
24.         }
    
25.         if (len == 0) {
    
26.                 start = n;
    
27.                 len = 1;
    
28.         }
    
29.         printf("%d\n",len);
    
30.         for (int i = 0; i < len; ++i) {
    
31.                 if (i) {
    
32.                         putchar('*');
    
33.                 }
    
34.                 printf("%d", start + i);
    
35.         }
    
36.         puts("");       
    
37.         return 0;
    
38. }
    

复制代码