首页 > 其他分享 >【假期刷些题-1】快速幂、递归幂次方、音速、快乐水

【假期刷些题-1】快速幂、递归幂次方、音速、快乐水

时间:2023-01-12 21:46:06浏览次数:67  
标签:音速 cout int ll long ans 次方 include 刷些

因为很久没刷算法题了手有点生,所以刷些题记录下
快速幂和取余运算

//取模运算的性质
(a*b)%p=[(a%p)*(b%p)]%p

快速幂模板题
https://www.luogu.com.cn/problem/P1226
对于本题来说,用这种方法让O(b)的算法复杂度变成了O(log2b)

#include<iostream>

using namespace std;

typedef long long ll;

ll fast_power(ll a,ll b,ll c){
	ll ans=1;
	a%=c;//防止a初始值过大
	while(b){//b不为0就循环
		if(b&1){//为奇数就让ans*a,让底数开平方,让指数缩小一半
			ans*=a;
			ans%=c;//由取模运算的性质
		}
		//偶数的话就不需要ans*a,直接让底数开平方,让指数缩小一半就行
		a*=a;
		a%=c;//由取模运算的性质
		b>>=1;
	}
	return ans;
}

int main(){
	
	ll a,b,c;
	
	cin>>a>>b>>c;
	
	cout<<a<<"^"<<b<<" mod "<<c<<"=";
	cout<<fast_power(a,b,c);
	
	return 0;
}

https://www.luogu.com.cn/problem/P1010
这个题嘞,乍一看好像能写,实际一写我就寄了,去看看佬们的代码
思路呢,模拟递归。
1、找到2的幂次方最接近n且小于n
2、让n减去这个2的幂次方
3、这个2的幂次方如果幂大于2就再对这个幂搜索
4、n减去2次幂之后还大于2就对n再搜索
5、如果n为0或1或2就结束

#include<iostream>

using namespace std;

typedef long long ll;

ll n;

void search(ll x){
	if(x!=0){
		cout<<2;//先输出一个2,再对后面进行添加 
		int q=1,p=0;//q为底数,p为指数 
		while(q<=x){//先找到小于x且最接近的2次幂 
			q*=2;
			++p;
		}
		--p;//实际上多加了一次,所以减去
		q/=2;//之前那个2的幂次方多乘了一次2
		if(p==0||p==2){
			cout<<"("<<p<<")";//进行特判,且p=1的时候不需要加括号 
		}
		if(p>=3){//只要比2大就继续搜索 
			cout<<"(";
			search(p);
			cout<<")";
		}
		x-=q;//减去少掉的部分
		if(x){
			cout<<"+";//如果x不为0的话,就后面添个+再搜索后续部分 
			search(x);
		}
	}
}
int main(){
	
	cin>>n;
	
	search(n);
	
	return 0;
}

哎呀,这思路帅啊
其实还是我太菜了
剩下还有其他思路,暂时不看了刷下一道去了
https://www.luogu.com.cn/problem/P6039
开始的时候一看,哎挺简单的,直接对着B点丢球过去然后求个x/y就行,然后写完,还没交,去看看别人的代码,好家伙咋还有这么多分析。
原来是我直接没考虑2*r大于OA,然后看了下别人的证明,也不算很难,把图一画还是明了的
在这里插入图片描述
啊还有就是没有考虑到x=0,y=0的情况哇,这种情况下任意方向丢传送器都可以,取最小的tan也就是取0的情况,这道题就算完成了
结果还是有些细节出错啊,还把Error打成ERROR哈哈

#include<iostream>
#include<cmath>
#include<cstdio>

using namespace std;

double x,y,r;

int main(){
	
	cin>>x>>y>>r;
	double ma=0;
	ma=sqrt(x*x+y*y);
	double ans=0;
	ans=abs(ma-2*r);//第一次忘了加绝对值了 
	printf("%.6lf\n",ans);
	if(x==0&&y==0){
		cout<<"0.00";
	}
	else if(y==0){
		cout<<"Error";//爷笑了这个整成ERROR了 
	}
	else{
		printf("%.2lf",abs(x/y));//这个也忘了还有绝对值 
	}
	return 0;
}

https://www.luogu.com.cn/problem/P6022
这道题竟然能靠我的脑子想出来,还真是不容易啊
虽然很简单
qwq

#include<iostream>

using namespace std;

int n,m,sum=0,summ=0;//sum代表每次喝的数字,summ代表兑换的数字 
long long ans=0;//最终喝掉的可乐 
int a[6],b[6];//a数组是附属品的兑换值,b是附属品的拥有值 

int main(){
	
	cin>>n>>m;
	
	for(int i=1;i<=m;++i){
		cin>>a[i];
	}
	sum=n;
	while(sum){
		summ=0;
		ans+=sum;//每轮都喝可乐 
		for(int i=1;i<=m;++i){
			b[i]+=sum;//附属品的增加 
			summ+=b[i]/a[i];//附属品兑换的可乐 
			b[i]=b[i]%a[i];//附属品的剩余 
		}
		if(summ>=n){//如果一轮获得的兑换可乐比最初都多就代表无限白嫖 
			cout<<"Inf";
			return 0;
		}
		sum=summ;//新的一轮能喝的可乐 
	}
	cout<<ans;
	return 0;
}

后续的话会尽量保持刷到开学

标签:音速,cout,int,ll,long,ans,次方,include,刷些
From: https://www.cnblogs.com/whynot-ne/p/17048006.html