本文主要是介绍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 本原串（快速幂+容斥原理）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
