Ivan_3569

468

Ivan_3569
3小时前

## 题解

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

const int N = 5010;

int primes[N], cnt;
bool st[N];
int sum[N];

void get_primes(int n)
{
for (int i = 2; i <= n; i ++)
{
if(!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; j ++ )
{
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int get(int n, int p)
{
int res = 0;
while(n)
{
res += n / p;
n /= p;
}
return res;
}
vector<int> mul(vector<int> &A, int b)
{
vector<int> C;
int t = 0;
for (int i = 0; i < A.size() || t ; i ++ )
{
if (i < A.size()) t += A[i] * b;
C.push_back(t % 10);
t /= 10;
}
while (C.back() == 0 && C.size() > 1) C.pop_back();

return C;
}

int main()
{
int a, b;
cin >> a >> b;

get_primes(a);

for (int i = 0; i < cnt; i ++ )
{
int p = primes[i];
sum[i] = get(a, p) - get(b, p) - get(a - b, p);
}

vector<int> res;
res.push_back(1);

for (int i = 0; i < cnt; i ++ )
for (int j = 0; j < sum[i]; j ++ )
res = mul(res, primes[i]);

for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]);
puts("");

return 0;
}


Ivan_3569
7小时前

#### 题解

#include <iostream>

using namespace std;

int main()
{
double x;
cin >> x;
double l = -100, r = 100;
while (r - l > 1e-8)
{
double mid = (l + r) / 2;
if (mid * mid * mid > x) r = mid;
else l = mid;
}
printf("%lf", l);
return  0;
}


Ivan_3569
8小时前

#### 二分模板

int q[N];
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}

int q[N];
int l = 0, r = n - 1;

while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) l = mid;
else r = mid - 1;
}


## 题解

#include <iostream>

using namespace std;

const int N = 100010;
int n;
int q[N];

int main()
{
int m;
cin >> n >> m;
for (int i = 0; i < n; i ++ )
cin >> q[i];
while(m -- )
{
int x;
cin >> x;
int l = 0, r = n - 1;
while(l < r)
{
int mid = l + r >> 1;
if (q[mid] >= x) r = mid;
else l = mid + 1;
}
if (q[l] != x) cout<<"-1 -1\n";
else
{
cout << l << " ";
l = 0, r = n - 1;

while (l < r)
{
int mid = l + r + 1 >> 1;
if (q[mid] <= x) l = mid;
else r = mid - 1;
}
cout << l << endl;
}
}

return 0;
}



Ivan_3569
20小时前

## 题解

int qmi(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}

return res;
}

int C(int a, int b)
{
int res = 1;
for(int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2)% p;
}
return res;
}

int lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}


Ivan_3569
21小时前

#### 模板

int p;
int qmi(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}

return res;
}

int C(int a, int b)
{
int res = 1;
for(int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2)% p;
}
return res;
}

int lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}


## 题解

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

int p;

int qmi(int a, int k)
{
int res = 1;
while(k)
{
if(k & 1) res = (LL)res * a % p;
k >>= 1;
a = (LL)a * a % p;
}

return res;
}

int C(int a, int b)
{
int res = 1;
for(int i = 1, j = a; i <= b; i ++, j -- )
{
res = (LL)res * j % p;
res = (LL)res * qmi(i, p - 2)% p;
}
return res;
}

int lucas(LL a, LL b)
{
if (a < p && b < p) return C(a, b);
return (LL)C(a % p, b % p) * lucas(a / p, b / p) % p;
}

int main()
{
int n;
cin >> n;
while(n -- )
{
LL a, b;
cin >> a >> b >> p;
cout << lucas(a, b) << endl;
}

return 0;
}


Ivan_3569
23小时前

## 题解


#include <iostream>
#include <algorithm>

using namespace std;

const int N = 100010, mod = 1e9 + 7;

typedef long long LL;

int fact[N], infact[N];

int qmi(int a, int k, int p)
{
int res = 1;
while (k)
{
if (k & 1) res = (LL) res * a % p;
a = (LL) a * a % p;
k >>= 1;
}
return res;
}

int main()
{
fact[0] = infact[0] = 1;
for (int i = 1; i < N; i ++)
{
fact[i] = (LL)fact[i - 1] * i % mod;
infact[i] = (LL)infact[i - 1] * qmi(i, mod - 2, mod) % mod;
}
int n;
cin >> n;
while(n --)
{
int a, b;
scanf("%d%d",&a, &b);
printf("%d\n",(LL)fact[a] * infact[b] % mod * infact[a - b] % mod);
}

return 0;

}


Ivan_3569
23小时前

#### 模板

void init()
{
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

}


## 题解

#include <iostream>
#include <algorithm>

using namespace std;

const int N = 2010, mod = 1e9 + 7;
int c[N][N];

void init()
{
for (int i = 0; i < N; i ++ )
for (int j = 0; j <= i; j ++ )
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j - 1] + c[i - 1][j]) % mod;

}

int main()
{
init();
int n;
cin >> n;
while (n -- )
{
int a, b;
cin >> a >> b;
cout << c[a][b] << endl;
}
return 0;
}



## 题解

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;

const int N = 110;
const double eps = 1e-6;
int n;
double a[N][N];

int gauss()
{
int c, r;// c 为列   r 为行
for (c = 0, r = 0; c < n; c ++ )// 枚举每一列
{
int t = r;//记录当前行
for (int i = r; i < n; i ++ ) // 寻找绝对值最大值
if (fabs(a[i][c]) > fabs(a[t][c]))
t = i;
if(fabs(a[t][c]) < eps) continue;//此列下面都是0  下一列开始

for (int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); //将最大值列 放入当前行
for(int i = n; i >= c; i -- ) a[r][i] /= a[r][c];//将当前行t 的c列置为1  从后往前消，否则第一项为1，无法消后项

for(int i = r + 1; i < n; i ++ )//将下面行的此列消为0
if (fabs(a[i][c]) > eps)//非零则消
for(int j = n; j >= c; j --)
a[i][j] -= a[r][j] * a[i][c];

r ++;
}//当枚举完c列时，r最大为n
if (r < n)
{
for (int i = r; i < n; i ++)
if (fabs(a[i][n]) > eps)
return 2;
return 1;
}
for (int i = n - 1; i >= 0; i -- )
for(int j = i + 1; j < n; j ++ )
a[i][n] -= a[i][j] * a[j][n];
return 0;
}

int main()
{
cin >> n;
for (int i = 0; i < n; i ++ )
for(int j = 0; j < n + 1; j ++ )
cin >> a[i][j];
int t = gauss();
if (t == 0)
{
for (int i = 0; i < n; i ++ ) printf("%.2lf\n", a[i][n]);
}
else if (t == 1) puts("Infinite group solutions");
else puts("No solution");

return 0;
}


## 题解

#include <iostream>
#include <algorithm>

using namespace std;

typedef long long LL;

LL exgcd(LL a, LL b,LL &x, LL &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
LL d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
int n;
cin >> n;

LL a1, m1;

cin >> a1 >> m1;

for (int i = 0; i < n; i ++)
{
LL a2, m2;
cin >> a2 >> m2;

LL k1, k2;
LL d = exgcd(a1, a2, k1, k2);
if((m2 - m1) % d)
{
break;
}

k1 *= (m2 - m1) / d;
LL t = a2 / d;
k1 = (k1 % t + t) % t;

m1 = a1 * k1 + m1;
a1 = abs(a1 / d * a2);
}
{
cout << (m1 % a1 + a1) % a1 << endl;
}
else puts("-1");
return 0;
}



## 题解

#include <iostream>
using namespace std;

typedef long long LL;

int exgcd(int a, int b, int &x, int &y)
{
if(!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}

int main()
{
int n;
cin >> n;
while(n --)
{
int a, b, m;
int x, y;
scanf("%d%d%d",&a, &b, &m);
int d = exgcd(a, m, x, y);
if (b % d != 0) puts("impossible");
else printf("%d\n",(LL)b / d * x % m);

}
return 0;
}