곱셈, 이분탐색

1.분할정복 

문제 : a를 b번 곱했을 때 c로 나눈 나머지를 구하세요

해결 :

b 를 2로 계속 나눠가면서 계산한다 

#include <iostream>
using namespace std;
using ll=long long;
ll ans=1;
ll c;
ll recur (ll a,ll b){
	if(b==1) return a%c;
	if(b%2==0) {
		ll x=recur(a%c,b/2);
		ans=x%c*x%c%c;
	}
	else {
		ll x=recur(a%c,b/2);
		ans=x%c*x%c*a%c%c;
	}
	return ans%c;
}
int main() {
	ll a,b;
	cin>>a>>b>>c;
	cout<<recur(a%c,b);
	return 0;
}

2. 이분탐색

#include <iostream>
#include <algorithm>
using namespace std;
using ll=long long;
ll a,b;
ll arr[1000001];
ll ans,sum;

bool solve(ll k){
   ll temp=0;
   for(int i=0;i<a;i++){
   	if(arr[i]>=k) break;
   	temp+=(k-arr[i]);
   }
   return temp>=b;
}
int main() {
   cin>>a>>b;
   ll c;
   for(int i=0;i<a;i++)
      cin>>arr[i];
   ll s= *min_element(arr, arr + a), e = *max_element(arr, arr + a);
   while(s<=e){
      ll mid=(s+e)/2;
      if(solve(mid)){
         s=mid+1;
      }
      else {
        e=mid-1;
      }
   }
   cout<<e;
   return 0;
}

정렬을 하지 않고 , * min_element, *max_element 사용할 수 있다.