HackerRank leonardo-and-lucky-numbers —— 模线性方程的通解

2019-04-14 12:47发布

站内文章 / 模拟电子
10373 0 1093
题目链接：https://vjudge.net/problem/HackerRank-leonardo-and-lucky-numbers


题解： 1.根据扩展欧几里得：7*x + 4*y = gcd(7,4) = 1，必有整数解，其中一组为（-1,2），通解为：（-1+4*k， 2-7*k）。 2.当：7*x + 4*y = n，其中一组解为（-n，2*n），通解为：（-n+4*k， 2*n-7*k）。 3.若要上式有解，则通解（-n+4*k， 2*n-7*k）中必须至少有一对非负的整数解。 4. x = -n+4*k >=0   &&   y =  2*n-7*k >=0 ，推出k的范围：  n/4<=k<=2n/7。然后再在这个范围内枚举k，得到x，y，x、y为非负数，并且7x+4y = n。

代码如下： #include #include #include #include #include #include #include #include #include #include #include #define ms(a,b) memset((a),(b),sizeof((a))) //#define LOCAL using namespace std; typedef long long LL; const int INF = 2e9; const LL LNF = 9e18; const int mod = 1e9+7; const int maxn = 200000+10; int main() { LL q, n; scanf("%lld",&q); while(q--) { LL x, y, k, n; int B = 0; scanf("%lld",&n); for(k = n/4-1; k<=(2*n)/7+1; k++) //除法可能除不尽，所以要左右各扩一个单位 { x = -1LL*n+1LL*4*k; y = 1LL*2*n-1LL*7*k; if(x<0 ||y<0) continue; if(7*x+4*y==n) { B = 1; break; } } if(B) puts("Yes"); else puts("No"); } }

热门文章