网站建设方案包括哪些内容,做软件的步骤,水果网站推广,昆明建个网站哪家便宜礼物
jzoj 2129
题目大意
有1……n,n个礼物盒#xff0c;第i个礼物盒有i个礼物#xff0c;现在让你选2个礼物盒#xff0c;使他是k的倍数
输入样例
1 1
3 2
5 2
50 50
0 0输出样例
0
1
4
24数据范围
20%的数据N100; 80%的数据K1000; 每个输入文件最多有200行…礼物
jzoj 2129
题目大意
有1……n,n个礼物盒第i个礼物盒有i个礼物现在让你选2个礼物盒使他是k的倍数
输入样例
1 1
3 2
5 2
50 50
0 0输出样例
0
1
4
24数据范围
20%的数据N100; 80%的数据K1000; 每个输入文件最多有200行输入数据。
解题思路
对于20%的数据我们可以直接暴力 对于80%的数据我们可以按%k得到的值来分类如果两个数%剩的值加在一起等于k那说明这两个数是合法的一对 正解 首先我们图文结合如下图 首先我们把nnn按kkk来分第2步 然后我们把n/kn/kn/k定为xxx 每一个k中都有一个被整除的第3步右侧那x个被整除的可以组成(x−1)∗x2\frac{(x-1)*x}{2}2(x−1)∗x对 然后剩下的k−1k-1k−1我们分为奇偶数第4步 奇数把中间除外的互相相乘得到h∗x∗xh*x*xh∗x∗x对h为一半每个余数都有x个数两个就有x∗xx*xx∗x对然后剩下的一个第5步和其他k中的中间相乘得到(x−1)∗x2\frac{(x-1)*x}{2}2(x−1)∗x对 偶数直接相乘 然后处理余数 不到一半或在一般前面的部分就直接和另一侧的x个数相配第6步 如果有中间1块就和前面xxx个中间1块相配第8步 大于一半的就和一半前的x1x1x1相配1是因为第6步使一半前的加上了1 注解题思路写地不好请见谅
代码
#includecstdio
#define min(a,b) (a)(b)?(a):(b)
using namespace std;
long long n,k,x,ys,h,ans;
int main()
{scanf(%lld %lld,n,k);while (nk){xn/k;//如解题思路ysn%k;//余数h(k-1)/2;//减去整除部分后的一半ansx*(x-1)/2x*x*h;//整除部分和普通部分if ((k-1)%2) ansx*(x-1)/2;//奇数的中间部分if (ys0) ans(min(ys,h))*x,ys-h;//余数的左边部分if (ys0(k-1)%2) ansx,ys--;//奇余数的中间部分if (ys0) ansys*(x1);//余数的右边部分printf(%lld\n,ans);scanf(%lld %lld,n,k);}return 0;
}
