yukicoder No.176 2種類の切手

問題はこちら
No.176 2種類の切手 - yukicoder

B円をi枚使うと、残りをA円で払うにはceil((T-B*i)/A)枚必要なので
支払い金額合計はB*i+ceil((T-B*i)/A)*Aとなる
よってiを0からceil(T/B)までループ……するとA=B=1,T=1e9のときにTLE
B円をA枚使うことはA円をB枚使うことと同じなので、iの範囲はA未満として良い。
このときループ回数はmax(T/B,A)となるので、A≦Bの条件と合わせると、A=Bの時に最大値√T=10^4.5をとる。
これは間に合う。

int main(){
	int a,b,t,temp,i,s=2e9;
	//自明な上界としてt+a（全てa円で払った時）があるので、仮最小値は2e9で十分
	scanf("%d%d%d",&a,&b,&t);
	for(i=0;i<=t/b&&i<a;i++){
		temp=b*i+(t-b*i+a-1)/a*a;
		//tempの値は高々t+aなのでオーバーフローしない
		if(s>temp)s=temp;
	}
	printf("%d",s);
	return 0;
}

ループ終了条件は、単にi<10^4.5として良い
なぜならi<aは偽になっても問題なく（これはただの枝刈り）
i<=t/bが偽になった時は、tempの値はt+b以上となり、自明な上界t+aより大きな値になるからである
ただしこの時tempの値はintの範囲に収まらないのでlong型を使い必要がある

long a,b,s,i,q;
main(t){
	for(scanf("%d%d%d",&a,&b,&t);i<4e4;s=!s|q<s?q:s)q=(t-b*i+a-1)/a*a+b*i++;
	s=!printf("%d",s);
}

114B