生活随笔
收集整理的這篇文章主要介紹了
2021算法竞赛入门班第八节课【数学】习题
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
目錄）
- 最大公約數(lcm)
- [NOIP2011]計算系數【組合數】
- 大水題【容斥定理】
最大公約數(lcm)
https://ac.nowcoder.com/acm/problem/16710
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
LL a
,b
;
LL
gcd(LL a
,LL b
){return b
?gcd(b
,a
%b
):a
;}
int main(void)
{cin
>>a
>>b
;cout
<<a
/gcd(a
,b
)*b
;return 0;
}
[NOIP2011]計算系數【組合數】
https://ac.nowcoder.com/acm/problem/16596
#include<bits/stdc++.h>
using namespace std
;
typedef long long int LL
;
const int N
=1010;
const int mod
=10007;
LL f
[N
][N
],a
,b
,k
,n
,m
;
void init()
{for(int i
=0;i
<N
;i
++){for(int j
=0;j
<=i
;j
++){if(j
==0) f
[i
][j
]=1;else f
[i
][j
]=(f
[i
-1][j
-1]+f
[i
-1][j
])%mod
;}}
}
LL
quick_mi(LL a
,LL b
)
{LL sum
=1;while(b
){if(b
&1) sum
=sum
*a
%mod
;b
>>=1;a
=(a
*a
)%mod
;}return sum
%mod
;
}
int main(void)
{cin
>>a
>>b
>>k
>>n
>>m
;init();cout
<<f
[k
][n
]*quick_mi(a
,n
)%mod
*quick_mi(b
,m
)%mod
;return 0;
}
大水題【容斥定理】
https://ac.nowcoder.com/acm/problem/15079
這里的話集合是4個。你會發現它們的加減規律，它是這樣的+ - + - .......
#include<bits/stdc++.h>
using namespace std
;
typedef unsigned long long int LL
;
LL n
,sum1
,sum2
,sum3
,sum4
;
int main(void)
{while(cin
>>n
){sum1
=n
/2+n
/5+n
/11+n
/13;sum2
=n
/(2*5)+n
/(2*11)+n
/(2*13)+n
/(5*11)+n
/(5*13)+n
/(11*13);sum3
=n
/(2*5*11)+n
/(2*5*13)+n
/(5*11*13)+n
/(2*11*13);sum4
=n
/(2*5*11*13); cout
<<n
-(sum1
-sum2
+sum3
-sum4
)<<'\n';}return 0;
}
總結
以上是生活随笔為你收集整理的2021算法竞赛入门班第八节课【数学】习题的全部內容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。
