2 条题解

  • 0
    @ 2025-10-8 17:11:50

    不妨设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
      @ 2025-10-8 17:11:42
      /*
      不妨设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
      上传者