#include <cstdio>
#include <cmath>
#include <queue>
#include <iostream>
#include <algorithm>
//一条路可以重复走多次
using namespace std;
const int N = 200070, inf = 0x3f3f3f3f;
struct Edg {
int to, val, nxt;
} e[N];
int n, m, cnt, d[N], D[N], head[N];
priority_queue < pair<int, int> > q;
void add(int from, int to, int val){
e[++cnt].to = to;
e[cnt].val = val;
e[cnt].nxt = head[from];
head[from] = cnt;
}
void dij(){
for (int i = 1; i <= n; ++i)
d[i] = D[i] = inf;
d[1] = 0;
q.push( make_pair(1,0) );
while( !q.empty() ){
int u = q.top().first, frontdis = -q.top().second; q.pop();
for (int i = head[u]; i; i = e[i].nxt) {
int v = e[i].to, dis = frontdis + e[i].val;
if ( d[v] > dis ) {
D[v] = d[v], d[v] = dis;
q.push( make_pair(v, -d[v]) );
}
if ( D[v] > dis && d[v] < dis ){
D[v] = dis;
q.push( make_pair(v, -D[v]) );
}
}
}
}
int main(){
scanf("%d %d", &n, &m);
for (int i = 1, u, v, w; i <= m; ++i) {
scanf("%d %d %d", &u, &v, &w);
add(u, v, w), add(v, u ,w);
}
dij();
printf("%d
", D[n]);
return 0;
}
#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1e6 + 70;
int n, cnt, phi[N], prime[N], vis[N];
int main(){
phi[1] = 1;
for (int i = 2; i <= N; ++i) {
if ( !vis[i] ) {
prime[++cnt] = i;
phi[i] = i - 1;
}
// phi[ a * b ] = phi[a] * phi[b];
for (int j = 1; j <= cnt && i * prime[j] <= N; ++j){
vis[ i * prime[j] ] = 1;
phi[ i * prime[j] ] = i%prime[j] ? (prime[j] - 1) * phi[i] :
prime[j] * phi[i];
}
}
int T, n;
scanf("%d", &T);
while ( T-- ) {
scanf("%d", &n);
printf("%d
", phi[n]);
}
return 0;
}
inv[N] = qpow(f[N], p - 2);
for (int i = N - 1; i >= 0; --i)
inv[i] = 1LL * inv[i + 1] % p * (i + 1) % p;
#include <cstdio>
#include <cmath>
using namespace std;
int gcd(int a, int b){
return b ? gcd(b, a % b) : a;
}
int main(){
int n, ans = 0;
scanf("%d", &n);
for (int i = 1, x; i <= n; ++i) {
scanf("%d", &x);
ans = gcd(ans, abs(x));
}
printf("%d
", ans);
return 0;
}
inv[1] = 1;
for (int i = 2; i <= n; ++i)
inv[i] = (p - p/i) * inv[p % i] % p;
错排公式
D[0] = 0, D[1] = 0, D[2] = 1;
for (int i = 3; i <= N; ++i)
D[i] = 1LL * (i - 1) * (D[i - 1] + D[i - 2]) % p;