题解 P3951 【小凯的疑惑】

2018-05-25 21:10:37


这里我提供暴力暴力!!30/60/100分代码 ==

宣传一下Blog www.aptx.xin


30分代码

暴力枚举+完全的照着样例模拟

复杂度是(n^2*m^2)的

只能过1≤a,b≤50 的数据

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define R register
using namespace std;
typedef long long ll;
bool pd(ll );
ll a,b;
ll ans;

int main() {
    scanf("%lld%lld",&a,&b);
    for(R ll i = 1;i <= a*b;++i) {
        if(pd(i)) continue;
        ans = max(i,ans);
    }
    printf("%lld\n",ans);
    return 0; 
}

bool pd(ll n) {
    for(R ll i = 0;n - i >= 0;i += a) {
        ll a1 = n - i;
        for(R ll j = 0;a1-j >= 0;j += b) {
            ll b2 = a1 - j;
            if(b2 == 0) return true;
        }
    }
    return false;
}

60分代码

我们发现pd函数完全可以优化掉一重循环,并且倒序枚举减少大量枚举量,

最慢复杂度是(nm^2)但理论比这个快不少,平均是(nm^2/2)的

能过 1≤a,b≤10^4的点

#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
#define R register
using namespace std;
typedef long long ll;
bool pd(ll );
ll a,b;
ll ans;

int main() {
    scanf("%lld%lld",&a,&b);
    for(R ll i = a*b;i >= 1;--i) {
        if(pd(i)) continue;
        else {
            printf("%d\n",i);
            return 0;
        }
    }
    return 0; 
}

bool pd(ll n) {
    if(n % a == 0 || n % b == 0) return true;
    for(R ll i = 0;n - i >= 0;i += a)
        if((n - i) % b == 0) return true;
    return false;
}

考场上很多大佬都是找规律做的,不会数论。。所以我们可以打表表找规律。有了暴力就可以对拍

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

typedef long long ll;

int main() {
    ll a,b;
    scanf("%lld%lld",&a,&b);
    printf("%lld\n",a*b-a-b);
    return 0;
}

宣传一下Blog www.aptx.xin