HDU - 2197 本原串 - c++编程基础

Description

由0和1组成的串中，不能表示为由几个相同的较小的串连接成的串，称为本原串，有多少个长为n（n<=100000000)的本原串？
答案mod2008.
例如，100100不是本原串，因为他是由两个100组成，而1101是本原串。

Input

输入包括多个数据，每个数据一行，包括一个整数n，代表串的长度。

Output

对于每个测试数据，输出一行，代表有多少个符合要求本原串，答案mod2008.

Sample Input

Sample Output

思路：从总的串里减去非本原串，非本原串可以有本原串组成，只有长度是n的约数就行了，当然还有考虑全0和全1的情况

#include 
  
   
#include 
   
     #include 
    
      #include 
     
       #include 
      
        #include 
        typedef long long ll; using namespace std; const int mod = 2008; map
        
          mp; int pow_mod(int a, int n) { int ans = 1; int tmp = a; while (n) { if (n & 1) ans = ans * tmp % mod; tmp = tmp * tmp % mod; n >>= 1; } return ans; } int cal(int x) { if (mp[x] != 0) return mp[x]; if (x == 1) return mp[x] = 2; int ans = pow_mod(2, x); ans = (ans - 2 + mod) % mod; for (int i = 2; i*i <= x; i++) { if (x % i != 0) continue; if (i * i == x) { ans -= cal(i); continue; } else { ans = (ans - cal(i) + mod) % mod; ans = (ans - cal(x/i) + mod) % mod; } } return mp[x] = (ans + mod) % mod; } int main() { int n; while (scanf("%d", &n) != EOF) { printf("%d\n", cal(n)); } return 0; }