|
题目链接：传送门
题目密码：202201150000
资料连接：
快速幂
逆元
容斥原理
扩展欧几里得
博弈论之取石子游戏的学习
题目内容:
这里是引用
数学问题
A - A^B Mod C
思路：这个题目首先能想到暴力，但是数据太大，所以不现实，因此用快速幂来解决，具体看上述链接
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=100100;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll pmod(ll a,ll b,ll c){
ll ans=1;
while(b){
if(b&1)ans=(ans*a)%c;
b>>=1;
a=a*a%c;
}
return ans;
}
int main(){
ll a,b,c;
cin>>a>>b>>c;
cout<<pmod(a,b,c);
return 0;
}
B - 逆元
思路：本身是直接进行求解逆元的，但是超时。就看了看网上的题解，链接如下：题解
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e9;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
map<ll,ll> in;
bool isprime(ll x)
{
for(ll i=2;i*i<=x;i++)
{
if(x%i==0)
return false;
}
return true;
}
int main(){
cin>>n;
if(!isprime(n)){
cout<<"AKCniubi"<<endl;
}
else{
cout<<n*(n-1)/2;
}
return 0;
}
C - 判决素数个数
思路：知道如何判别一个数是否时素数即可。这里用的素数筛，另外x和y的谁大谁小不确定
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
ll pri[maxn+10],v[maxn+10];
ll m;
void prime(){
v[1]=1;
for(int i=2;i<=maxn;i++){
if(v[i]==0){
v[i]=i;
m++;
pri[m]=i;
}
for(int j=1;j<=m&&(i*pri[j]<=maxn);j++){
v[i*pri[j]]=pri[j];
if(i%pri[j]==0)break;
}
}
}
int main(){
prime();
ll x,y;
scanf("%lld%lld",&x,&y);
if(x>y){
ll t=x;
x=y;
y=t;
}
ll ans=0;
for(int i=x;i<=y;i++){
if(v[i]==i&&i!=1){
ans++;
}
}
printf("%lld\n",ans);
return 0;
}
D - 矩阵乘法
思路：了解下矩阵乘法就会了
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,m,k;
ll a[110][110],b[110][110],d[110][110];
int main(){
cin>>n>>m>>k;
for(int i=1;i<=n;i++){
for(int j=1;j<=m;j++){
cin>>a[i][j];
}
}
for(int i=1;i<=m;i++){
for(int j=1;j<=k;j++){
cin>>b[i][j];
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
for(int h=1;h<=m;h++){
d[i][j]+=a[i][h]*b[h][j];
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=k;j++){
cout<<d[i][j]<<" ";
}
cout<<endl;
}
return 0;
}
H - 互质数的个数（一）
思路：首先时了解互质的概念，其次是利用欧拉函数求结果
推导过程：
欧拉公式：phi(x) = (p1-1)/p1*(p2-1)/p2…(pn-1)/pn * x
推导过程如下：
x=p1^k1 p2k2*……pnkn ,对于某个数m=a^b(a为质数)，与m不互质的数只有a的倍数,即m/a,即a ^ (b-1),所以与m互质的个数为m-m/a=a ^ b-a^(b-1);
类似地，
phi(x)=[p1^ k1-p1^(k1-1)] * [p2^ k2-p2^ (k2-1)]……[pn ^ kn-pn^(kn-1)]
=[p1^(k1-1) * (p1-1)] * [p2^(k2-1)(p2-1)]……* [pn^(kn-1)*(pn-1)]
=[p1^ (k1-1) * p2^ (k2-1)……pn^(kn-1)][(p1-1) * (p2-1) * …… * (pn-1)]
=x * [(p1-1) * (p2-1)… * (pn-1)]/[(p1-1) * (p2-1) * …… *(pn-1)]
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll t;
ll solve(ll n){
ll ans=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
ans=ans/i*(i-1);
for(;n%i==0;n/=i);
}
}
if(n!=1){
ans=ans/n*(n-1);
}
return ans;
}
int main(){
scanf("%lld",&t);
ll n;
while(t--){
scanf("%lld",&n);
printf("%lld\n",solve(n));
}
return 0;
}
I - Sumdiv
思路：
约数和公式：
对于已经分解的整数A=(p1 ^ k1) * (p2 ^ k2) * (p3 ^ k3)… * (pn^kn)
有A的所有因子之和为
S = (1+p1+p1 ^ 2+p1 ^ 3+…p1^k1) * (1+p2+p2 ^ 2+p2 ^ 3+….p2^k2) * (1+p3+ p3 ^ 3+…+ p3^k3) * … * (1+pn+pn ^ 2+pn ^ 3+…pn^kn)
等比数列计算：直接用二分递归求：举例来说，1+a+a ^ 2+a ^ 3+a ^ 4=(1+a) * (1+a2)+a2;(1+a)=1(1+a)。根据奇偶二分下去。只要只有一个数为止。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=9901;
ll n,m;
struct node{
ll x,y;
}p[maxn];
ll pmod(ll x,ll y){
ll res=1;
while(y){
if(y&1){
res=res*x%mod;
}
x=x*x%mod;
y>>=1;
}
return res;
}
ll update(ll pn,ll pm){
if(pm==0){
return 1;
}
if(pm&1){
return update(pn,pm/2)*(1+pmod(pn,pm/2+1))%mod;
}else{
return (update(pn,pm/2-1)*(1+pmod(pn,pm/2+1))+pmod(pn,pm/2))%mod;
}
}
int main(){
while(scanf("%lld%lld",&n,&m)!=EOF){
ll k=0;
for(int i=2;i*i<=n;){
if(n%i==0){
k++;
p[k].x=i;
p[k].y=0;
while(n%i==0){
p[k].y++;
n/=i;
}
}
if(i==2){
i++;
}else{
i+=2;
}
}
if(n!=1){
k++;
p[k].x=n;
p[k].y=1;
}
ll ans=1;
for(int i=1;i<=k;i++){
ans=(ans*update(p[i].x,p[i].y*m)%mod)%mod;
}
printf("%lld\n",ans);
}
return 0;
}
J - The Lottery
思路:用二进制进行枚举所有情况，采用容斥原理去重，其中进行反面考虑，a的倍数有n/a个；既是a,也是b的倍数，即lcm(a,b)的倍数有n/lcm(a,b)个。是a,b,c的倍数，即lcm(a,b,c)的倍数有n/lcm(a,b,c)个。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=9901;
ll t,k,n,m;
ll a[maxn];
ll gcd(ll a,ll b){
return b ? gcd (b,a%b) : a;
}
ll lcm(ll a,ll b){
ll t=gcd(a,b);
return a/t*b;
}
int main(){
while(cin>>n>>m){
for(int i=0;i<m;i++){
cin>>a[i];
}
ll sum=0;
for(int i=1;i<(1<<m);i++){
ll cnt=0;
ll ans=1;
for(int j=0;j<m;j++){
if(i&(1<<j)){
ans=lcm(ans,a[j]);
if(ans>n){
break;
}
cnt++;
}
}
if(cnt&1){
sum+=n/ans;
}else{
sum-=n/ans;
}
}
cout<<n-sum<<endl;
}
return 0;
}
K - 组合数问题
思路：首先进行预处理，防止超时。理解组合数的运算，即C(n,m)=C(n-1,m-1)+C(n-1,m),然后简单的动态规划
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=9901;
ll t,k;
ll n,m;
ll a[2010][2010],num[2010][2010];
void init(){
a[1][1]=1%k;
if(a[1][1]==0)num[1][1]=1;
for(int i=2;i<2001;i++){
a[i][1]=i%k;
if(a[i][1]==0)num[i][1]=1;
for(int j=2;j<=i;j++){
a[i][j]=(a[i-1][j-1]+a[i-1][j])%k;
if(a[i][j]==0){
num[i][j]=num[i][j-1]+1;
}else{
num[i][j]=num[i][j-1];
}
}
}
}
int main(){
cin>>t>>k;
init();
while(t--){
cin>>n>>m;
int ans=0;
for(int i=1;i<=n;i++){
ll t=i;
if(m<i){
t=m;
}
ans+=num[i][t];
}
cout<<ans<<endl;
}
return 0;
}
L - 同余方程
思路:ax≡1(modb) 可以通过变化得到ax+kb=gcd(a,b)，因为一定有解，这个就是扩展欧几里得原理的结果
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=9901;
ll a,b,x=0,y=0;
void exgcd(ll a,ll b,ll &x,ll &y){
if(!b){
x=1,y=0;
}else{
exgcd(b,a%b,x,y);
ll t;
t=x,x=y,y=t-a/b*y;
}
}
int main(){
cin>>a>>b;
exgcd(a,b,x,y);
cout<<(x%b+b)%b;
return 0;
}
博弈题目
E - Bash游戏
思路：
1.n<=k,A必赢 ，n=k+1,B必赢
2.k+1<n<=（2k+1）时A只需拿n-(k+1)（必定小于等于K）个，A必赢
3.n=2(k+1)时，无论A拿多少个，假设x个，此时n-x>=k+2,B只需拿(n-x-(k+1))个即可，B必赢
4.以此类推
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,k;
int main(){
ll t;
cin>>t;
while(t--){
cin>>n>>k;
if(n%(k+1)){
cout<<"A"<<endl;
}else{
cout<<"B"<<endl;
}
}
return 0;
}
F - 取石子游戏
思路：属于威佐夫博奕(Wythoff Game)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n,k;
double x = (sqrt(5.0) + 1)/2.0;
int main(){
ll a,b;
while(cin>>a>>b){
ll t=abs(b-a);
if(a>b){
ll k=a;
a=b;
b=a;
}
if((int)(t*x)==a){
cout<<"0"<<endl;
}else{
cout<<"1"<<endl;
}
}
return 0;
}
G - Matches Game
思路：当异或和为奇数时，先手先拿，拿完后，后手无论怎么拿，先手一定拿和后手一样的，一定可以拿到最后。当异或和为偶数时，无论先手怎么拿，后手只需拿一样的，一定可以拿到最后
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long int ll;
typedef pair<ll,ll> P;
const int maxn=1e5+10;
const int inf=0x3f3f3f3f3f;
const int maxm=5e4+5;
const int mod=1000000007;
ll n;
int main(){
while(cin>>n){
ll ans=0;
for(int i=1;i<=n;i++){
ll x;
cin>>x;
ans=ans^x;
}
if(ans){
cout<<"Yes"<<endl;
}else{
cout<<"No"<<endl;
}
}
return 0;
}
|