石景山网站开发,评价一个网站的优缺点,网站开发调试工具,聊城做网站费用这次差不多有6道是我现在可以做的#xff0c;还有一道博弈论加大数的以后再补吧#xff0c;还是要多积累啊。
现在先补充两个题目的吧
1006 Detachment
这道题题意很简单#xff0c;求把N分成任意个和为N的数字#xff0c;求这些数字乘积最大是多少。
首先要知道肯…这次差不多有6道是我现在可以做的还有一道博弈论加大数的以后再补吧还是要多积累啊。
现在先补充两个题目的吧
1006 Detachment
这道题题意很简单求把N分成任意个和为N的数字求这些数字乘积最大是多少。
首先要知道肯定是把N分成 234567.......这种相邻的数字乘积最大只要求 a a1 a2 ~ ad和为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对于1e97的逆元就是 exgcd(2, 1e97, 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的时候要单独考虑一下。 #includebits/stdc.h
using namespace std;#define LL long long
const LL mod 1e97;
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,sum100000,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]*(n2) % mod) * inv2 % mod);}else {int s n - va1;LL inv2 f(s);//printf(%d %d %I64d\n,s,n,mul[n1]);printf(%I64d\n,(mul[n1] % mod) * inv2 % mod);}//printf(%I64d\n,sum[n]);}
}1004 A Simple Math Problem
这道题要知道一个基本的数论的定理gcd(x,y) gcd(xy , lcm(x,y))。
这样就可以知道 a*b y/gcd(x,y) , ab x;
两个方程两个未知数求解二元一次方程即可。 #includebits/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 (nss)/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);}
}
