HPY_数论

A lightoj1214 (取模)

非常简单,每一位表示一下模一下,秒了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
char str[999];
int main(){
int T;scanf("%d",&T);
for(int x=1;x<=T;++x){
ll m,ans=0;
printf("Case %d:",x);
scanf("%s%lld",str,&m);
int len=strlen(str);
for(ll i=len-1,wei=1;i>=0;--i){
if(str[i]=='-') continue;
ll now,k=str[i]-'0';
now=(((wei)%m)*(k%m))%m;
ans=(ans+now)%m;
wei=(wei*10)%m;
}
if(ans%m) printf(" not divisible\n");
else printf(" divisible\n");
}
return 0;
}

B hdu2197 思维题

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

很显然非本原串更好求,可以用总数-非本串个数,怎么减呢。感觉肯定是需要用到之前的答案对吧(类似于递推)。实际上不就是找循环节么。它的每个循环节的长度就是它的长度的因数对吧。假设n=8,它的因数有1,2,4.

先看1,{1/1/1/1/1/1/1/1}和{0/0/0/0/0/0/0/0} 减去。

看2:{11/11/11/11},{00/00/00/00},{10/10/10/10},{01/01/01/01}.

很显然后两个{01}和{10}也是2的本原串。一起减掉4?然而和1有重复对吧.因为我们是从小到大看的,而前两个可以在1的时候减掉,所以,只要减掉后两个,也就是2的本原串个数就行了。对于它的非本原串来说,它们一定能有循环节更小的表示方法,而那些我们肯定在之前已经减过了。4也是同理。所以只要从小到大减去每个因子的本原串个数就行了,因为它们是不可再分的。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <cstdio>
#include <vector>
#include <map>
using namespace std;
typedef long long ll;
map<ll,ll> p;
typedef map<ll,ll>::iterator it;
const ll mod = 2008;
ll pow2(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1) ans=ans*a%mod;
return ans;
}
ll solve(ll n)
{
if(p.count(n)) return p[n];
ll ans=pow2(2LL,n);
for(ll i=1;i*i<=n;++i)
{
if(n%i==0){
ans=(ans-solve(i)+mod)%mod;
if(i*i<n&&i>1)
ans=(ans-solve(n/i)+mod)%mod;
}
}
p[n]=ans;
return ans;
}
int main()
{
p[0]=0,p[1]=2,p[2]=2;
ll n;
while(~scanf("%lld",&n))
{
printf("%lld\n",solve(n));
}
return 0;
}

C

D hdu5019

对gcd分解因子,然后排序。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
const ll maxn = 1e6+100;
const ll inf = 1e13;
vector<ll> v;
inline ll fast_pow(ll a,ll b){
ll ans=1;
for(;b;b>>=1,a*=a){
if(b&1) ans*=a;
}
return ans;
}
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
void factor(ll n){
for(ll i=2;i*i<=n;++i){
if(n%i==0){
v.push_back(i);
if(i*i<n) v.push_back(n/i);
}
}
v.push_back(n);if(n!=1) v.push_back(1);
}
int main(){
int T;scanf("%d",&T);
while(T--){
v.clear();
ll a,b,k;scanf("%lld%lld%lld",&a,&b,&k);
ll g=gcd(max(a,b),min(a,b));
factor(g);
sort(v.begin(),v.end());
// printf("size:%d\n",v.size()-k);
ll sz=v.size()-k;
if(sz>=0LL) printf("%lld\n",v[sz]);
else printf("-1\n");
}
return 0;
}

E hdu4549 (矩阵快速幂 费马小定理)

首先看题,显然F[n]=b^(f(n))*a^(f(n-1))%mod,f(n)表示斐波那契数列(f(1)=f(2)=1)

然后肯定要用矩阵快速幂求对吧。构建矩阵快速幂的矩阵:{ {1,1},{1,0} } (并不会用latex之类的…)

注意快速幂时还要有一个单位矩阵,是{ {1,0},{0,1} }

因为一开始忘了矩阵乘法的乘法顺序所以自己定义了一下,不过好像反了(逃)。以及矩阵乘法里懒得写第三层循环直接枚举元素…总之代码里透露着各种不规范…

然而1e9的斐波那契数列早大到不知哪里去了,于是用费马小定理。快速的说就是a^b%mod==a^(b%(mod-1))%mod.

为什么?根据费马小定理可以知道x^(p-1)%p=1,设x等于a^b,原式等价于a^(b*(p-1))%p=a^(0).

此时可以看出b*(p-1)这个是有p-1的因子的a的幂,而且原式%p之后幂就变成了0,这不就相当于b*(p-1)%(p-1)么…

所以在矩阵快速幂里%(mod-1)就行了…

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <cstdio>
#include <algorithm>
#include <vector>
typedef long long ll;
const ll mod = 1000000007;
struct cb4{
ll c[2][2];
};
inline cb4 mult(cb4 a,cb4 b){
cb4 ans;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j)
ans.c[i][j]=((a.c[0][i]%(mod-1))*(b.c[j][0]%(mod-1))%(mod-1)
+(a.c[1][i]%(mod-1))*(b.c[j][1]%(mod-1))%(mod-1))%(mod-1);
}
return ans;
}
const cb4 std_cb=(cb4){{{1,0},{0,1}}};
const cb4 fp_cb=(cb4){{{1,1},{1,0}}};
cb4 fast_pow(cb4 a,ll b){
cb4 ans=std_cb;
for(;b;b>>=1,a=mult(a,a)){
if(b&1) ans=mult(ans,a);
}
return ans;
}
ll fast_pow(ll a,ll b){
ll ans=1;a%=mod;
for(;b;b>>=1,a=(a*a)%mod){
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
ll a,b,n;
while(~scanf("%lld%lld%lld",&a,&b,&n)){
cb4 ai={{{1,0},{0,0}}};
if(n==0) printf("%lld\n",a);
else if(n==1) printf("%lld\n",b);
else{
cb4 fei=mult(ai,fast_pow(fp_cb,n-1));
printf("%lld\n",fast_pow(b,fei.c[0][0]%mod)*fast_pow(a,fei.c[0][1])%mod);
}
}
return 0;
}

最后:矩阵快速幂时间复杂度n^3log(n)

F cf450b 矩阵快速幂

矩阵快速幂模板题。把矩阵快速幂的矩阵改成 { {1,-1},{1,0} } 就行了。

不过要注意,如果是负数,要%成正的.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <cstdio>
#include <algorithm>
#include <vector>
typedef long long ll;
const ll mod = 1000000007;
struct cb4{
ll c[2][2];
};
inline cb4 mult(cb4 a,cb4 b){
cb4 ans;
for(int i=0;i<2;++i){
for(int j=0;j<2;++j)
{
ans.c[i][j]=((a.c[0][j]%(mod))*(b.c[i][0]%(mod))%(mod)
+(a.c[1][j]%(mod))*(b.c[i][1]%(mod))%(mod))%(mod);
while(ans.c[i][j]<0)
ans.c[i][j]=(ans.c[i][j]+mod)%mod;
}
}
return ans;
}
const cb4 std_cb=(cb4){{{1,0},{0,1}}};
const cb4 fp_cb=(cb4){{{1,-1},{1,0}}};
cb4 fast_pow(cb4 a,ll b){
cb4 ans=std_cb;
for(;b;b>>=1,a=mult(a,a)){
if(b&1) ans=mult(a,ans);
}
return ans;
}
ll fast_pow(ll a,ll b){
ll ans=1;a%=mod;
for(;b;b>>=1,a=(a*a)%mod){
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
ll a,b,n;
scanf("%lld%lld%lld",&a,&b,&n);
cb4 ai={{{b,0},{a,0}}};
if(n==1) printf("%lld\n",(a+mod)%mod);
else{
cb4 fei=mult(ai,fast_pow(fp_cb,n-2));
ll ans=fei.c[0][0];
//printf("%lld %lld\n%lld %lld\n",fei.c[0][0],fei.c[0][1],fei.c[1][0],fei.c[1][1]);
printf("%lld\n",(ans+mod)%mod);
}
return 0;
}

G hdu5651 排列组合

给一个串,看能组成几个回文串。

首先统计一下每个字母的个数。如果有多个字母的个数为奇数的数量>1,那没法回文。因为如果只有一个字母的个数为奇数,那么放到中间就行啦。

如果可以,那么就能回文,然后只要找出其中一半有多少种组成就行了。问题转化为算一下带有重复元素的全排列。公式:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const ll mod = 1e9+7;
ll Getaii(ll n)
{
ll ans=1;
for(ll i=1;i<=n;++i) ans=ans*i%mod;
return ans;
}
ll fast_pow(ll a,ll b)
{
ll ans=1;
for(;b;b>>=1,a=a*a%mod)
{
if(b&1) ans=ans*a%mod;
}
return ans;
}
int main()
{
int T;scanf("%d",&T);
while(T--){
ll sz[26]={0};
char ch;
while((ch=getchar())<'a'||ch>'z');
while(ch>='a'&&ch<='z') ++sz[ch-'a'],ch=getchar();
ll cnt=0,tot=0;
for(int i=0;i<26;tot+=sz[i],++i) if(sz[i]%2) ++cnt;
if(cnt>1) {printf("0\n");continue;}
ll ans=Getaii(tot/2);
for(int i=0;i<26;++i){
if(sz[i]==0) continue;
ans=ans*fast_pow(Getaii(sz[i]/2),mod-2LL)%mod;
}
printf("%lld\n",ans);
}
return 0;
}

H hdu2200 排列组合

因为之前没读题,所以请好好读读题目:

Eddy是个ACMer,他不仅喜欢做ACM题,而且对于Ranklist中每个人的ac数量也有一定的研究,

他在无聊时经常在纸上把Ranklist上每个人的ac题目的数量摘录下来,然后从中选择一部分人(或者全部)按照ac的数量分成两组进行比较,

他想使第一组中的最小ac数大于第二组中的最大ac数,但是这样的情况会有很多,聪明的你知道这样的情况有多少种吗? 

从中选择一部分人,所以是C(n,k), 使第一组中的最小ac数大于第二组中的最大ac数,所以只要在序列里切一刀就行了(k-1).所以这个题就看你会不会求组合数就行了。

注意这个组合数非递推的求法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <cstdio>
#include <algorithm>
using namespace std;
typedef long long ll;
ll C(ll n,ll a){
ll ans=1;
for(ll i=1;i<=a;++i)
ans=ans*(n-i+1)/i;
return ans;
}
int main()
{
ll n;
while(~scanf("%lld",&n)){
ll ans=0;
for(ll i=1;i<=n;++i){
ans+=C(n,i)*(i-1);
}
printf("%lld\n",ans);
}
return 0;
}

I hdu1465 排列组合

错排公式模板题

错排公式:每个都恰好不对的所有可能情况
D(i)=(i-1)*(d(i-1)+d(i-2)) D(1)=0,D(2)=1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
ll a[30]={0,0,1};
ll C[30][30];
int main()
{
for(ll i=3;i<=20;++i) a[i]=(i-1)*(a[i-1]+a[i-2]);
ll n;
while(~scanf("%lld",&n)){
printf("%lld\n",a[n]);
}
return 0;
}

J hdu1796 容斥定理

类似于noip初赛的某道题:1~n中不能被2,3,5整除的数有多少个。考点当然是容斥定理。

首先算出能整除的,然后用总数减掉。具体请看代码。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include <cstdio>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
ll gcd(ll a,ll b)
{
return b?gcd(b,a%b):a;
}
int main()
{
ll n,m;
while(~scanf("%lld%lld",&n,&m))
{
ll ans=0;
vector<ll> v;
for(int i=1;i<=m;++i) {ll t;scanf("%lld",&t);if(t>0) v.push_back(t);}
m=v.size();
for(ll i=1;i<(1LL<<m);++i)
{
ll x=1;
int cnt=0;
for(ll j=0;j<m;++j){
if((i>>j)&1LL){
++cnt;x=x*v[j]/gcd(x,v[j]);
}
}
if(cnt%2==1) ans+=(n-1)/x;
else ans-=(n-1)/x;
}
printf("%lld\n",ans);
}
return 0;
}