昨天晚上卡B题了，掉大分，qwq
现在回想起来昨天没反应过来
题目要求为公司节省最多的钱
我们可以发现如果n个人，每个人的分的钱都小于g/2且者n个人分的钱加起来恰好为k*g的话则公司一分钱都不用花
第一种情况
假设每个人分的钱都为h则最理想的情况为h*n>=k*g且h<g/2，即h=g/2-1
如果符合这个条件的话就可以直接输出总数k*g
第二种情况
如果每个人分的钱均小于g/2但是总数加起来不够的话
分析可得每个人分的钱h(i)=a(i)*g+r(i)
h(1)+...+h(n)=k*g
(a(1)+...+a(n))*g+r(1)+...+r(n)=k*g
∑r(i)=(k-∑a(i))*g
由此可以看出个余数之和一定为g的倍数，第一种情况下a(i)全为0即都是小于g/2的数
所以我们为了节省更多的钱尽量向第一种情况靠近即求得不大于(g/2-1)*n的g的最大倍数,使得∑r最大，∑a最小
#include <iostream>
using namespace std;
const int N=1e5+10;
typedef long long ll;
ll t,n,k,g;
int main(){
cin>>t;
while(t--){
cin>>n>>k>>g;
ll sum1=k*g;
int h=g/2+g%2-1;//如果g为奇数则g/2是可以取的
ll sum2=h*n;
if(sum2>=sum1){
cout<<sum1<<endl;
}
else{
cout<<sum2/g*g<<endl;
}
}
}