#include <bits/stdc++.h>
#define int long long
using namespace std;
int qmi(int a,int k)
{
int ans=1;
while(k)
{
if(k&1)ans=ans*a%200907;
a=a*a%200907;
k>>=1;
}
return ans;
}
signed main()
{
int n;
cin>>n;
while(n--)
{
int a,b,c,k;
cin>>a>>b>>c>>k;
if(b-a==c-b) //等差数列
cout<<(a+(k-1)*(b-a))%200907<<endl;
else //等比数列
{
int ak=a*qmi(b/a,k-1);
cout<<ak%200907<<endl;
}
}
}
活动打卡代码
AcWing 1289. 序列的第k个数（算法提高课）
活动打卡代码
AcWing 3625. 幂次方（每日一题）
#include <bits/stdc++.h>
#define int long long
using namespace std;
signed main()
{
int a,k,ans=1;
cin>>a>>k;
while(k)
{
if(k&1)ans=ans*a%233333;
a=a*a%233333;
k>>=1;
}
cout<<ans<<endl;
}
活动打卡代码
AcWing 875. 快速幂（算法基础课）
#include <bits/stdc++.h>
#define int long long
using namespace std;
int n;
int qmi(int a,int k,int m)
{
int ans=1;
while(k)
{
if(k&1)ans=ans*a%m;
a=a*a%m;
k>>=1;
}
return ans;
}
signed main()
{
cin>>n;
while(n--)
{
int a,k,m;
cin>>a>>k>>m;
cout<<qmi(a,k,m)<<endl;
}
}
斜率相同就能在一个直线上
#include <bits/stdc++.h>
using namespace std;
map<double,int>mp;
int main()
{
int n,x0,y0;
cin>>n>>x0>>y0;
while(n--)
{
int x,y;
cin>>x>>y;
double k=(y0-y)/((x0-x)*1.0);
if(k>=1e5||k<=-1e5)k=fabs(k);
mp[k]++;
}
cout<<mp.size();
}
活动打卡代码
AcWing 4309. 消灭老鼠（每日一题）
#include <bits/stdc++.h>
using namespace std;
map<double,int>mp;
int main()
{
int n,x0,y0;
cin>>n>>x0>>y0;
while(n--)
{
int x,y;
cin>>x>>y;
double k=(y0-y)/((x0-x)*1.0);
if(k>=1e5||k<=-1e5)k=fabs(k);
mp[k]++;
}
cout<<mp.size();
}
活动打卡代码
AcWing 872. 最大公约数（算法基础课）
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int a,int b)
{
return b==0?a:gcd(b,a%b);
}
int main()
{
int n,a,b;
cin>>n;
while(n--)
{
cin>>a>>b;
cout<<gcd(a,b)<<endl;
}
}
活动打卡代码
AcWing 1292. 哥德巴赫猜想（算法提高课）
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
int prime[N],st[N],cnt=0;
void get_prime(int n)
{
for(int i=2;i<=n;i++)
{
if(!st[i])prime[cnt++]=i;
for(int j=0;prime[j]*i<=n;j++)
{
st[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
int n;
get_prime(N-1);
while(cin>>n,n)
{
for(int i=1;;i++)
{
int a;
a=n-prime[i];
if(!st[a])
{
printf("%d = %d + %d\n",n,prime[i],a);
break;
}
}
}
}
活动打卡代码
AcWing 3792. 质数问题（每日一题）
#include <bits/stdc++.h>
using namespace std;
const int N=1e3+10;
int cnt,st[N],prime[N];
vector<int>_prime;
void get_prime(int n)
{
for(int i=2;i<=N;i++)
{
if(!st[i])prime[cnt++]=i;
for(int j=0;prime[j]<=n/i;j++)
{
st[prime[j]*i]=1;
if(i%prime[j]==0)break;
}
}
}
int main()
{
int t;
cin>>t;
get_prime(N-1);
while(t--)
{
int n,k,res=0;
cin>>n>>k;
for(int i=0;prime[i]<=n;i++)
{
for(int j=0;prime[j+1]<=prime[i];j++)
{
if(prime[i]==prime[j]+prime[j+1]+1)
{
res++;
break;
}
}
}
if(res>=k)cout<<"YES"<<endl;
else cout<<"NO"<<endl;
}
}
活动打卡代码
AcWing 1215. 小朋友排队（蓝桥杯辅导课）
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long a[N],c[N],b[N];
int n;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int v)
{
for(int i=x;i<=N;i+=lowbit(i))c[i]+=v;
}
int query(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))ans+=c[i];
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]++;
}
for(int i=1;i<=n;i++)
{
add(a[i],1);
b[i]=i-query(a[i]);
}
memset(c,0,sizeof c);
for(int i=n;i>=1;i--)
{
add(a[i],1);
b[i]+=query(a[i]-1);
}
long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=(b[i]+1)*b[i]/2;
}
cout<<ans<<endl;
}
活动打卡代码
AcWing 1215. 小朋友排队
这里树状数组维护的高度，add中到N
#include <bits/stdc++.h>
using namespace std;
const int N=1e6+10;
long long a[N],c[N],b[N];
int n;
int lowbit(int x)
{
return x&-x;
}
void add(int x,int v)
{
for(int i=x;i<=N;i+=lowbit(i))c[i]+=v;
}
int query(int x)
{
int ans=0;
for(int i=x;i;i-=lowbit(i))ans+=c[i];
return ans;
}
int main()
{
cin>>n;
for(int i=1;i<=n;i++)
{
cin>>a[i];
a[i]++;
}
for(int i=1;i<=n;i++)
{
add(a[i],1);
b[i]=i-query(a[i]);
}
memset(c,0,sizeof c);
for(int i=n;i>=1;i--)
{
add(a[i],1);
b[i]+=query(a[i]-1);
}
long long ans=0;
for(int i=1;i<=n;i++)
{
ans+=(b[i]+1)*b[i]/2;
}
cout<<ans<<endl;
}
