xs

3151

rd0
wKingYu

Lansong
Shanjw
ohh_0

OI

815741912
codewin

BT7274
wwdxwjl

77777777777
TongX_5c

Joey就是小许
.Alex.

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

typedef long long LL;

int n;

int main()
{
cin >> n;

LL ans = n;
for(int i = 2; i <= n / i; i ++)
{
if(n % i == 0)
{
int p = i, cnt = 0;
while(n % p == 0) cnt ++, n /= p;

ans = ans * (p +  1ll * cnt * p - cnt) / p;
}
}

if(n != 1) ans = ans * (n + 1ll * n - 1) / n;
cout << ans << endl;

return 0;

}


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

int a, p, b;

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 bsgs(int a, int p, int b)
{
if(1 % p == b % p) return 0;

int k = sqrt(p) + 1;
unordered_map<int, int> hash;
for(int i = 0, w = b % p; i < k; i ++, w = 1ll * w * a % p)
hash[w] = i;

int ak = 1;
for(int i = 1; i <= k; i ++) ak = 1ll * ak * a % p;

for(int i = 1, w = ak % p; i <= k; i ++, w = 1ll * w * ak % p)
if(hash.count(w)) return k * i - hash[w];
return -1e9;
}

int exbsgs(int a, int p, int b)
{
//逆元x可能为负，这里的b也可能是负数
b = (b % p + p) % p;
if(1 % p == b % p) return 0;

int x, y;
int d = exgcd(a, p, x, y);
if(d == 1) return bsgs(a, p, b);

if(b % d) return -1e9;
//x是(a/d) 关于 (p/d)的逆元，可能为负数
exgcd(a / d, p / d, x, y);
return 1 + exbsgs(a, p / d, 1ll * b / d * x % (p / d));
}

int main()
{
while(cin >> a >> p >> b , a || p || b)
{
int res = exbsgs(a, p, b);
if(res < 0) puts("No Solution");
else cout << res << endl;
}

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;
int p, a, b, x1, t;

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 qmi(int x, int k)
{
int res = 1 % p;
while(k)
{
if(k & 1) res = 1ll * res * x % p;
x = 1ll * x * x % p;
k >>= 1;
}

return res % p;
}

int BSGS(int a, int b, int p)
{
if(1 == b % p) return 0;

int k = sqrt(p) + 1;
//y:[0 ~ k-1]；x:[1 ~ k]; t = xk - y
unordered_map<int, int> hash;
for(int i = 0, res = b % p; i < k; i ++, res = 1ll * res * a % p)
hash[res] = i;

int ak = 1;
for(int i = 1; i <= k; i ++)
ak = 1ll * ak * a % p;

for(int i = 1, res = ak; i <= k; i ++, res = 1ll * res * ak % p)
if(hash.count(res)) return i * k - hash[res];
return -2;
}

int main()
{
int tt;
cin >> tt;
while(tt --)
{
cin >> p >> a >> b >> x1 >> t;
if(a == 0)
{
if (x1 == t) puts("1");
else if (b == t) puts("2");
else puts("-1");
}
else if(a == 1)
{
if (b == 0) puts(t == x1 ? "1" : "-1");
else
{
int x, y;
exgcd(b, p, x, y);
x = ((LL)x * (t - x1) % p + p) % p;
cout << x + 1 << endl;
}
}
else
{
int C = (LL)b * qmi(a - 1, p - 2) % p;
int A = (x1 + C) % p;
if(A == 0)
{
int u = (-C + p) % p;
puts(u == t ? "1" : "-1");
}
else
{
int B = (t + C) % p;
cout << BSGS(a, (LL)B * qmi(A, p - 2) % p, p) + 1 << endl;
}
}

}

return 0;
}


# 多组输入时如何初始化字典树

void add(int x)
{
int cnt = 0;
for(int i = 17; i >= 0; i --)
{
int t = ((x >> i) & 1);
if(!son[cnt][t])
{
//在插入时更新字典树。
son[idx + 1][0] = son[idx + 1][1] = 0;
son[cnt][t] = ++ idx;
}
cnt = son[cnt][t];
}
val[cnt] = x;
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>

using namespace std;

const int N = 5e5 + 10;
const double PI = acos(-1);

struct Complex
{
double x, y;
Complex operator + (const Complex &t) const
{
return {x + t.x, y + t.y};
}
Complex operator - (const Complex &t) const
{
return {x - t.x, y - t.y};
}
Complex operator * (const Complex &t) const
{
return {x * t.x - y * t.y, x * t.y + y * t.x};
}
}a[N], b[N];
int tot, bit, tra[N];

void FFT(Complex a[], int type)
{
for(int i = 0; i < tot; i ++)
if(i < tra[i]) swap(a[i], a[tra[i]]);

for(int mid = 1; mid < tot; mid *= 2)
{
Complex w1 = {cos(PI / mid), type * sin(PI / mid)};
for(int pos = 0, len = mid * 2; pos < tot; pos += len)
{
Complex wk = {1, 0};
for(int k = 0; k < mid; k ++, wk = wk * w1)
{
auto x = a[k + pos], y = wk * a[k + pos + mid];
a[k + pos] = x + y, a[k + pos + mid] = x - y;
}
}
}

if(type == 1) return;
for(int i = 0; i < tot; i ++ ) a[i].x /= tot;
}

int main()
{
string s1, s2;
cin >> s1 >> s2;
int n = s1.size(), m = s2.size();
n --, m --;

while((1 << bit) <= n + m) bit ++;
tot = 1 << bit;

for(int i = 0; i < tot; i ++)
tra[i] = (tra[i >> 1] >> 1) | ((i & 1) << (bit - 1));

reverse(s1.begin(), s1.end());
reverse(s2.begin(), s2.end());

for(int i = 0; i <= n; i ++) a[i].x = s1[i] - '0';
for(int i = 0; i <= m; i ++) b[i].x = s2[i] - '0';

FFT(a, 1), FFT(b, 1);
for(int i = 0; i < tot; i ++) a[i] = a[i] * b[i];
FFT(a, -1);

vector<int> ans(n + m + 1);
for(int i = 0; i <= n + m; i ++) ans[i] = (int)(a[i].x + 0.5);

vector<int> t;
for(int i = 0, tt = 0; (i <= n + m) || tt; i ++)
{
if(i <= n + m)
tt += ans[i];
t.push_back(tt % 10);
tt /= 10;
}

int idx = n + m + 1;
while(t[idx] == 0 && idx >= 1) idx --;
for(int i = idx; i >= 0; i --) cout << t[i];

return 0;
}



#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
const int N = 5e5 + 10;
const double PI = acos(-1);

struct Complex
{
double x, y;
Complex operator + (const Complex &t) const
{
return {x + t.x, y + t.y};
}
Complex operator - (const Complex &t) const
{
return {x - t.x, y - t.y};
}
Complex operator * (const Complex &t) const
{
return {x * t.x- y * t.y, y * t.x + x * t.y};
}
}a[N], b[N];

int tot, bit, tra[N];
int n, m;

void FFT(Complex a[], int type)
{
for(int i = 0; i < tot; i ++)
if(i < tra[i]) swap(a[i], a[tra[i]]);

for(int mid = 1; mid < tot; mid <<= 1)
{
auto w1 = Complex ({cos(PI / mid), type * sin(PI / mid)});
for(int len = mid * 2, pos = 0; pos < tot; pos += len)
{
auto wk = Complex ({1, 0});
for(int k = 0; k < mid; k ++, wk = wk * w1)
{
auto x = a[pos + k], y = a[pos + k + mid];
a[pos + k] = x + wk * y;
a[pos + k + mid] = x - wk * y;
}
}
}

if(type == 1) return;
for(int i = 0; i < tot; i ++ ) a[i].x /= tot;
}

int main()
{
scanf("%d%d", &n, &m);
// cout << n << m << endl;
for(int i = 0; i <= n; i ++) scanf("%lf", &a[i].x);
for(int i = 0; i <= m; i ++) scanf("%lf", &b[i].x);

while((1 << bit) <= n + m) bit ++;
tot = 1 << bit;

//1101 0110 0110 1011(处理蝴蝶变化数组)
for(int i = 0; i < tot; i ++) tra[i] = (tra[i >> 1] >> 1) | ((i & 1) << (bit - 1));

FFT(a, 1), FFT(b, 1);//将系数表示转换为点表示
for(int i = 0; i < tot; i ++) a[i] = a[i] * b[i];//a * b
FFT(a, -1);//将点表达在转换为系数表示

for(int i = 0; i <= n + m; i ++)
printf("%d ", (int)(a[i].x + 0.5));

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int P = 10007;

int main()
{
string s;
cin >> s;
int n = 0;
//秦九韶算法，将一个n次多项式，一直提取x将其变为：n次乘法和n次加法。
for(auto x : s)
n = (n * 10 + (x - '0')) % P;
cout << 1ll * n * (n + 1) * (n + 2)  / 6 % P << endl;

return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e4 + 10, M = 210, P = 1e9 + 7;
LL s[N][M];
LL c[M][M];

void init()
{
s[0][0] = 1;
for(int i = 1; i < N; i ++)
for(int j = 1; j < M; j ++) s[i][j] = (s[i - 1][j - 1] + 1ll * (i - 1) * s[i - 1][j]) % P;

c[0][0] = 1;
for(int i = 1; i < M; i ++)
for(int j = 0; j < M; j ++)
if(!j) c[i][j] = 1;
else c[i][j] = (c[i - 1][j] + c[i - 1][j - 1]) % P;
}

int main()
{
init();
int tt;
cin >> tt;
while(tt --)
{
int n, a, b;
cin >> n >> a >> b;
// cout << s[n - 1][a + b - 2] << ' ' << c[a + b - 2][a - 1] << endl;
cout << 1ll * s[n - 1][a + b - 2] * c[a + b - 2][a - 1] % P << '\n';
}
}


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

typedef long long LL;
const int N = 1010, P = 1e9 + 7;
int S[N][N];
int n, m;

void init()
{
S[0][0] = 1;
for(int i = 1; i <= n; i ++)
for(int j = 1; j <= m; j ++)
S[i][j] = (S[i - 1][j - 1] + 1ll * j * S[i - 1][j]) % P;
}

int main()
{
cin >> n >> m;
init();

cout << S[n][m] << endl;
return 0;
}


#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int N = 1010, mod = 1e9 + 7;
int s[N][N];

void init()
{
s[0][0] = 1;
for(int i = 1; i < N; i ++)
for(int j = 1; j < N; j ++)
s[i][j] = (s[i - 1][j - 1] + 1ll * (i - 1) * s[i - 1][j]) % mod;
}

int main()
{
init();
int n, k;
cin >> n >> k;
cout << s[n][k] << endl;

return 0;
}