题解 P3951 【小凯的疑惑】

这里我提供**暴力暴力！！**30/60/100分代码 == 宣传一下Blog www.aptx.xin ------------ 30分代码 暴力枚举+完全的照着样例模拟 复杂度是（n^2*m^2）的 只能过1≤a,b≤50 的数据 ```cpp #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函数完全可以优化掉一重循环，并且倒序枚举减少大量枚举量， 最慢复杂度是（n*m^2）但理论比这个快不少，平均是（n*m^2/2）的 能过 1≤a,b≤10^4的点 ```cpp #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; } ``` ------------ 考场上很多大佬都是找规律做的，不会数论。。所以我们可以打表表找规律。有了暴力就可以**对拍**。  ```cpp #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