2 条题解
-
0
不妨设a1<a2<a3<a4。显然第一问的答案是4,满足a1+a4=a2+a3,a1+a2|a3+a4,a1+a3|a2+a4。容易发现将其同时扩大k倍是仍然满足条件的,于是考虑gcd(a1,a2,a3,a4)=1的情况。对于a1+a3|a2+a4,由a1+a4=a2+a3,可以发现a2+a4<3(a1+a3),因为2a3>a4且a2<a3,于是也就有a2+a4=2(a1+a3)。然后考虑a1+a2|a3+a4,为保证a2+a4=2(a1+a3),a2和a3大约至多在a1和a4的三等分点取得,于是a2+a4<5(a1+a3)。将a2+a4=4(a1+a3)和a2+a4=3(a1+a3)代入解方程即可,得到的都是和a1的整数倍关系,其中4倍时为1 11 19 29,3倍时为1 5 7 11(样例都很良心的给出来了)。那么合法集合就是这些数的倍数了。勉勉强强推出来了,发现这是个IMO题时非常震惊。
#include <bits/stdc++.h> using namespace std; #define ll long long ll l, r; int main() { cin >> l >> r; cout << 4 << endl << r/11 - min(r/11, l-1) + r/29 - min(r/29, l-1); return 0; } -
0
/* 不妨设a1<a2<a3<a4。显然第一问的答案是4,满足a1+a4=a2+a3,a1+a2|a3+a4,a1+a3|a2+a4。容易发现将其同时扩大k倍是仍然满足条件的,于是考虑gcd(a1,a2,a3,a4)=1的情况。对于a1+a3|a2+a4,由a1+a4=a2+a3,可以发现a2+a4<3(a1+a3),因为2a3>a4且a2<a3,于是也就有a2+a4=2(a1+a3)。然后考虑a1+a2|a3+a4,为保证a2+a4=2(a1+a3),a2和a3大约至多在a1和a4的三等分点取得,于是a2+a4<5(a1+a3)。将a2+a4=4(a1+a3)和a2+a4=3(a1+a3)代入解方程即可,得到的都是和a1的整数倍关系,其中4倍时为1 11 19 29,3倍时为1 5 7 11(样例都很良心的给出来了)。那么合法集合就是这些数的倍数了。勉勉强强推出来了,发现这是个IMO题时非常震惊。 */ #include<bits/stdc++.h> using namespace std; #define ll long long ll l,r; int main() { cin>>l>>r; cout<<4<<endl<<r/11-min(r/11,l-1)+r/29-min(r/29,l-1); return 0; }
- 1
信息
- ID
- 6584
- 时间
- 1000ms
- 内存
- 128MiB
- 难度
- 10
- 标签
- 递交数
- 1
- 已通过
- 1
- 上传者