首页 > 代码库 > bzoj4915 简单的数字题

bzoj4915 简单的数字题

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=4915

【题解】

出自第52届IMO试题第1题。
技术分享

首先第一问一定是4,如果要你证明,我们可以设四个数为a1,a2,a3,a4

不妨令a1<a2<a3<a4

那么有S=a1+a2+a3+a4

S/2=a1/2+a2/2+a3/2+a4/2

那么有a3/2+a4/2+a3/2+a4/2>a1/2+a2/2+a3/2+a4/2>S/2,即a3+a4>S/2,显然这不可能是S的因数。

同理,a2/2+a4/2+a2/2+a4/2>a1/2+a2/2+a3/2+a4/2>S/2,即a2+a4>S/2,显然也不可能是S的因数。

所以在所有6种组合里,最多有4种数对满足条件。

 

讨论当nA=4的情况:

a1+a4和a2+a3一定有一个大于等于S/2

讨论a2-a1和a4-a3的大小即可.

也就是说

S/2<=max(a1+a4,a2+a3)

那么要满足a1+a4是S的约数,a2+a3是S的约数,就要满足

a1+a4=a2+a3=S/2

令u=a1+a2,v=a1+a3(u<v)

那么S=2(a2+a3)=2(u+v-2a1)

所以v|S,即v|2(u+v-2a1),即v|2(u-2a1)

那么令k=(2u-4a1)/v,k为整数且k>=1

那么k=2(u/v)-4(a1/v)<2

又k>0,且k为整数且k>=1,故k=1

2(u-2a1)=v

另一边,有u|2(v-2a1)

那么就有u|2(2(u-2a1)-2a1)

u|2(2u-6a1)

u|4u-12a1

那么u|12a1

由于u<v=2u-4a1

所以u>4a1

所以u=6a1或u=12a1

所以集合只有两种,为S={a1,5a1,7a1,11a1}或S={a1,11a1,19a1,29a1}

暴力做即可

技术分享
# include <stdio.h>
# include <string.h>
# include <iostream>
# include <algorithm>
// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int M = 5e5 + 10;
const int mod = 1e9+7;

# define RG register
# define ST static

ll l, r;

int main() {
    cin >> l >> r;
    cout << 4 << endl;
    ll ans = max(r/11-l+1, 0ll) + max(r/29-l+1, 0ll);
    cout << ans << endl; 
    return 0;
}
View Code

 

bzoj4915 简单的数字题