HDU 2197 本原串（快速幂+容斥原理）

本文主要是介绍HDU 2197 本原串（快速幂+容斥原理），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

本原串

Time Limit: 1000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 1771    Accepted Submission(s): 612

 

Problem Description

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

 

 

Input

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

 

 

Output

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

 

 

Sample Input

1

2

3

4

Sample Output

2

2

6

12

 

 

长度为n的本源串的个数 = 2^n - 长度为n的非本源串,对于长度为n的非本源串一定是由长度为m的串循环k次得到的,

故m一定是n的约数 即( n%m==0 )     所以只需要求 所有n的约数长度 所构成的本源串个数

公式 F[n]=2^n-ΣF[i]-2;  //  减去2 是全为0 和 1的情况

// 快速幂+容斥原理+递推求解#include<iostream>
#include<cstring>
using namespace std; 
#define ll long long int
int ans[100000009];
ll q_pow( ll b ){ll ans1=1;ll a=2;while( b ){if( b&1 )ans1= (ans1*a)%2008;a =(a*a)%2008;b>>=1;} return ans1;
} 
ll cal( ll n ){if( ans[n] )return ans[n]; if( n==1 )return 2;ll res=q_pow(n);for( ll i=2;i*i<=n;i++){if( n %i==0){res = ( res-cal(i) + 2008) %2008;if( i*i!=n)res= ( res - cal( n/i) +2008)%2008;}}return ans[n] = ( res-2+2008)%2008;
} 
int main(void){long long n;while( scanf("%lld",&n) !=EOF ){printf("%lld\n",cal(n));}return 0;
}

 

 

 

这篇关于HDU 2197 本原串（快速幂+容斥原理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---