平凡的函数
题目描述
题解
直接线性筛即可, 然后记录一下质因子的幂数。
code
#include <cstdio>
#include <cctype>
#include <cmath>
#include <iostream>
using namespace std;
#define print(x) cerr << #x << " : " << x << endl;
inline int read() {
int k = 0, f = 1; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
return k * f;
}
const int maxn = 5e7 + 100;
int prime[maxn], vis[maxn], f[maxn];
signed main() {
#ifdef local
freopen("in", "r", stdin);
#else
freopen("func.in", "r", stdin);
freopen("func.out", "w", stdout);
#endif
int n = read(), cnt = 0;
long long ans = 1;
f[1] = 1;
for (int i = 2; i <= n; i++) {
if (!vis[i]) prime[++cnt] = i, f[i] = i ^ 1;
for (int j = 1; i * prime[j] <= n; j++) {
vis[i * prime[j]] = 1;
if (i % prime[j] == 0) {
int x = i, m = 1;
while (x % prime[j] == 0) x /= prime[j], ++m;
f[i * prime[j]] = f[x] * (prime[j] ^ m);
break;
}
f[i * prime[j]] = f[i] * f[prime[j]];
}
ans += f[i];
}
printf("%lld\n", ans);
return 0;
}
那一天她离我而去
题目描述
她走的悄无声息,消失的无影无踪。
至今我还记得那一段时间,我们一起旅游,一起游遍山水。到了最终的景点,她却悄无声息地消失了,只剩我孤身而返。
现在我还记得,那个旅游区可以表示为一张由n
个节点m
条边组成无向图。我故地重游,却发现自己只想尽快地结束这次旅游。我从景区的出发点(即 1 号节点)出发,却只想找出最短的一条回路重新回到出发点,并且中途不重复经过任意一条边。
即:我想找出从出发点到出发点的小环。
题解
- 暴力思路:将所有与起点相连的边删除,从这些相连的点跑到其他相连点的最短路尝试更新答案
- 正解思路:对暴力进行优化,分组进行最短路, 因为任意两个不同的点,二进制一定至少存在一位不同,我们以每个二进制位的0,1进行分组,每组点组成的环一定被至少一次更新,于是可以达到目的, 复杂度 \(O(m log^2n)\)
code
暴力
#include
using namespace std;
const int maxn = 1e4 + 5, maxm = 4e4 + 5;
const int Inf = 0x3f3f3f3f;
struct node { int to, next, dis; } e[maxm<<1];
int head[maxn], ecnt;
void add(int a,int b,int c){ e[ecnt] = (node){b, head[a], c}; head[a] = ecnt++; }
int vis[maxn], dis[maxn];
void Spfa(int x){
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
queue q;
q.push(x); dis[x]=0;
while(!q.empty()){
int u = q.front(); q.pop();
vis[u] = 0;
for(int i = head[u]; ~i; i=e[i].next){
int v = e[i].to, d;
if(dis[v] > (d = dis[u] + e[i].dis)) {
dis[v] = dis[u] + e[i].dis;
if(!vis[v]) q.push(v), vis[v] = 1;
}
}
}
}
int main(){
#ifndef debug
freopen("leave.in", "r", stdin);
freopen("leave.out", "w", stdout);
#endif
int T; scanf("%d",&T);
while(T--){
int n, m; scanf("%d%d", &n, &m);
memset(head, -1, sizeof(head));
ecnt = 0;
for(int i = 1; i <= m; i++){
int u, v, dis; scanf("%d%d%d", &u, &v, &dis);
add(u, v, dis), add(v, u, dis);
}
int ans = Inf;
for(int i = head[1]; ~i; i = e[i].next) {
int temp = e[i].dis;
e[i].dis = e[i ^ 1].dis = Inf;
Spfa(1);
ans = std::min(ans, dis[e[i].to] + temp);
e[i].dis = e[i ^ 1].dis = temp;
}
if(ans == Inf) printf("-1\n");
else printf("%d\n", ans);
}
}
#include
using namespace std;
#define print(x) cerr << #x << " : " << x << endl;
inline int read() {
int k = 0, f = 1; char ch = getchar();
for(; !isdigit(ch); ch = getchar()) if(ch == '-') f = -1;
for(; isdigit(ch); ch = getchar()) k = k * 10 + ch - '0';
return k * f;
}
const int maxn = 3e4 + 100;
struct node { int to, next, dis; } e[maxn * 8];
struct edge { int to, dis; } g[maxn * 8];
int head[maxn], ecnt = 0;
inline void add(int u, int v, int d) { e[++ecnt] = (node) {v, head[u], d}; head[u] = ecnt; }
int dis[maxn], vis[maxn];
priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;
inline void dijkstra(int s) {
memset(vis, 0, sizeof(vis)), memset(dis, 0x3f, sizeof(dis));
dis[s] = 0;
q.push(make_pair(0, s));
while (q.size()) {
int x = q.top().second;
q.pop();
if (vis[x]) continue;
for (register int i = head[x]; i; i = e[i].next) {
int y = e[i].to, d;
if (dis[y] > (d = dis[x] + e[i].dis)) {
dis[y] = d;
q.push(make_pair(dis[y], y));
}
}
}
}
int main() {
#ifndef debug
freopen("leave.in", "r", stdin);
freopen("leave.out", "w", stdout);
#endif
int T = read();
while(T--) {
int n = read(), m = read();
memset(head, 0, sizeof(head));
ecnt = 1;
int ans = 0x3f3f3f3f;
int gcnt = 0;
for (register int i = 1; i <= m; i++) {
int x = read(), y = read(), z = read();
if(x > y) swap(x, y);
if(x == 1) g[++gcnt] = (edge){y, z};
else add(x, y, z), add(y, x, z);
}
int tot = n;
for(int i = 1; i <= n; i <<= 1) {
int s = ++tot, t = ++tot;
for(int j = 1; j <= gcnt; j++) {
if(g[j].to & i) add(s, g[j].to, g[j].dis);
else add(g[j].to, t, g[j].dis);
}
dijkstra(s);
ans = min(ans, dis[t]);
}
if (ans == 0x3f3f3f3f) printf("-1\n");
else printf("%d\n", ans);
}
return 0;
}