Problem D: Power Strings

code

6 年前

时间： 1ms 内存：128M

描述：

Problem D: Power Strings

Given two strings a and b we define a*b to be their concatenation. For example, if a = "abc" and b = "def" then a*b = "abcdef". If we think of concatenation as multiplication, exponentiation by a non-negative integer is defined in the normal way: a^0 = "" (the empty string) and a^(n+1) = a*(a^n).

Each test case is a line of input representing s, a string of printable characters. For each s you should print the largest n such that s = a^n for some string a. The length of s will be at least 1 and will not exceed 1 million characters. A line containing a period follows the last test case.

输入：

输出：

示例输入：

abcd
aaaa
ababab
.

示例输出：

1
4
3

提示：

参考答案（内存最优[748]）：

#include <stdio.h>

main(){
   int n,i,sum;
   while (1 == scanf("%d",&n) && n) {
      sum = n;
      for (i=2;i*i <= n;i++) {
         if (n%i == 0) {
            sum -= sum/i;
         }
         while (n%i == 0) n /= i;
      }
      if (n > 1) sum -= sum/n;
      printf("%d\n",sum);
   }
}

参考答案（时间最优[0]）：

#include <stdio.h>

main(){
   int n,i,sum;
   while (1 == scanf("%d",&n) && n) {
      sum = n;
      for (i=2;i*i <= n;i++) {
         if (n%i == 0) {
            sum -= sum/i;
         }
         while (n%i == 0) n /= i;
      }
      if (n > 1) sum -= sum/n;
      printf("%d\n",sum);
   }
}

题目和答案均来自于互联网，仅供参考，如有问题请联系管理员修改或删除。