佛山外贸网站建设效果免费网站建设seo
这次差不多有6道是我现在可以做的，还有一道博弈论加大数的以后再补吧，还是要多积累啊。
现在先补充两个题目的吧
1006 Detachment
这道题题意很简单，求把N分成任意个和为N的数字，求这些数字乘积最大是多少。
首先要知道肯定是把N分成 2，3，4，5，6，7.......这种相邻的数字乘积最大，只要求 a + a+1 + a+2 ~ a+d和为N的乘积。
主要用到两个数组，一个存2到N的和，另外一个存2到N的乘积，乘的时候mod一下就好了。
还有一个知识是当 a/b ，a被mod过后，除出来来的结果是错的，mod只有在乘法的情况下才可以，那么就求一下b 的逆元，再把a*（b的逆元）即可。
这里先贴出两种求逆元的办法：
1、a与mod互素：
ll exgcd(ll a, ll b, ll &x, ll &y)
{if (b == 0){x = 1;y = 0;return a;}ll r = exgcd(b, a % b, x, y);ll t = x % mod;x = y % mod;y = ((t - a / b * y) % mod + mod) % mod;return r;
}求2对于1e9+7的逆元就是 exgcd(2, 1e9+7, x, y),其中x的值就是inv2，2、mod为素数：
ll power_mod(ll a, ll b, ll mod)
{ll ans = 1;while (b){if (b & 1) ans = ans * a % mod;a = a * a % mod;b >>= 1;}return ans;
}
inv2 = power_mod(a, mod - 2, mod);这里mod为素数，直接b^(mod-2)即可，求的时候用快速幂。
知道这些就可以做了，要注意N为1的时候要单独考虑一下。
#include<bits/stdc++.h>
using namespace std;#define LL long long
const LL mod = 1e9+7;
LL sum[100005],mul[100005]; //sum 2到N的和，mul 2到N的积LL f(LL x) { //求x的逆元LL ans = 1;int t = mod-2;while(t) {if(t & 1 ) ans = ans*x%mod;x = x*x%mod;t >>= 1;}return ans;
}int main() {int t;scanf("%d",&t);LL dd = 0,d = 1;for(int i = 2;i < 100005;i++) { dd += i;sum[i] = dd;d = d*i%mod;mul[i] = d;}while(t--) {LL x;scanf("%I64d",&x);if(x == 1) {printf("1\n");continue;}int n = lower_bound(sum,sum+100000,x) - sum;if(sum[n] != x) n--;LL va = x - sum[n];if(va > n-1) {LL inv2 = f(2);printf("%I64d\n",(mul[n]*(n+2) % mod) * inv2 % mod);}else {int s = n - va+1;LL inv2 = f(s);//printf("%d %d %I64d\n",s,n,mul[n+1]);printf("%I64d\n",(mul[n+1] % mod) * inv2 % mod);}//printf("%I64d\n",sum[n]);}
}
1004 A Simple Math Problem
这道题要知道一个基本的数论的定理：gcd(x,y) = gcd(x+y , lcm(x,y))。
这样就可以知道 a*b = y/gcd(x,y) , a+b = x;
两个方程两个未知数，求解二元一次方程即可。
#include<bits/stdc++.h>
using namespace std;#define LL long longint main() {int n,m;while(scanf("%d%d",&n,&m) != EOF) {int dd = __gcd(n,m),flag = 0;LL x = dd*m;if(n*n - 4*x >= 0) { //即二元一次方程有解LL ss = sqrt(n*n - 4*x);LL a = (n+ss)/2;LL b = n-a;if(a/(__gcd(a,b))*b == m) printf("%I64d %I64d\n",b,a); //输出要注意大小的顺序，不然会waelse printf("No Solution\n");}else printf("No Solution\n");}
}