企业官网建设流程全解析

1.练习项目 ：

问题描述

有 n 个传送阵，编号为 1∼n，每个传送阵使用若干块 "星石" 作为能源。"星石" 是一种很神奇的物质，一块 "星石" 的能量值等于它的价值。同时，星石放在一起会激发更强大的能量，例如：有 3 块 "星石" 的能量值分别为 2,3,4，则它们放在一起可以提供的能量为 2×3×4=24，需要消耗的价值为 2+3+4=9。

现在每个传送阵都有一个能量值 x， f(x) 是构成 x 的星石最小价值之和对 n 取模加一，换句话说便是 f(x)=(sum modn)+1，sum 是构成 x 的星石最小价值之和。

例如：

x=9,n=997,f(x)=(3+3)mod997+1=7。

而两个传送阵可以相互传送的规则如下：

1. 如果两个传送阵的 f(x) 相等，则两个传送阵可以相互传送。例如 n>6,x=8,x=9 便可以相互传送。
2. 能量值为 x 的传送阵可以和编号为 f(x) 的传送阵相互传送。例如 n>6,a[4]=9（a[4] 是假设 4 号传送阵能量为 9），所以 4 号传送阵可以和 7 号传送阵能相互传送。因为 4 号传送阵的能量值为 9，f(x)=(3+3modn)+1=7。

给定每个传送阵都有的能量值 x，你需要求出从编号 a 到编号 b 的最少传送次数，若不能到达，请输出 -1。

输入格式

第 1 行输入 3 个正整数，表示 n,a,b，含义为传送阵的数量，起点编号与终点编号。

第 2 行输入 n 个正整数 x，表示每个传送阵的能量值。

输出格式

输出 1 行，表示 a 到 b 的最少传送次数，若不能从 a 传送到 b 则输出 -1。

2.选择课程

在蓝桥云课中选择题库，选择题号6281并开始练习。

3.开始练习

（1）源码 ：

#include<bits/stdc++.h>

using namespace std;

using ll = long long;

const int N = 1e5+10;

vector<int>primes;

ll f[N];

void euler(int n)

{

bitset<(int)1e8+10>vis;

vis[0]=vis[1]=true;

for(int i=2;i<=n;i++){

if(!vis[i])primes.push_back(i);

for(int j=0;j<primes.size()&&i*primes[j]<=n;j++){

vis[i*primes[j]]=true;

if(i%primes[j]==0)break;

}

}

}

ll F(ll x,int n)

{

ll res=0;

for(int i=0;i<primes.size()&&primes[i]<=x/primes[i];i++){

ll prime = primes[i];

while(x%prime==0)res+=prime,x/=prime;

}

if(x>1)res+=x;

return res%n+1;

}

struct Edge{

int x,w;

bool operator < (const Edge &u)const{

if(w ^ u.w)return w>u.w;

return x<u.x;

}

};

vector<Edge>g[2*N];

const ll inf=2e18;

ll d[2*N];

void dijkstra(int st,int n)

{

for(int i=1;i<=2*n;i++)d[i]=inf;

bitset<2*N>vis;

priority_queue<Edge>pq;

pq.push({st,d[st]=0});

while(pq.size()){

int x=pq.top().x;pq.pop();

if(vis[x])continue;

vis[x]=true;

for(const auto &t:g[x]){

int y=t.x,w=t.w;

if(d[y]>d[x]+w){

pq.push({y,d[y]=d[x]+w});

}

}

}

}

int main()

{

ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);

int n,a,b;cin>>n>>a>>b;

euler(1e8);

for(int i=1;i<=n;i++){

ll x;cin>>x;

f[i]=F(x,n);

g[i].push_back({f[i],1});

g[f[i]].push_back({i,1});

}

//虚拟源点

for(int i=1;i<=n;i++){

g[i].push_back({n+f[i],0});

g[n+f[i]].push_back({i,1});

}

dijkstra(a,n);

cout<<(d[b]==inf?-1:d[b])<<'\n';

return 0;

}

（2）检验结果

对此代码进行检验，检验后无报错，提交此代码，判题结果为正确100分。

（3）练习心得：注意每段代码末尾的分号是否存在 ，如不存在则需即使补充；输入法 是否切换 为英语模式；语法是否错误。