A. 上海

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

---

题目描述

$\text{Shintaro}$ 有一个正整数 $k$。

请你判断是否存在正整数 $n$ ，使得 $n^2$ 是 $k$ 的倍数，且 $n$ 不是 $k$ 的倍数。如果存在，则输出最小的 $n$。不存在则输出 $-1$。

输入格式

一行一个数 $k$。

输出格式

一行一个数表示答案。

样例输入1

4

样例输出1

2

样例输入2

42

样例输出2

-1

数据范围

• 对于 $50\%$ 的数据：$1\le k\le 10^6$；
• 对于 $100\%$ 的数据：$1\le k\le 10^{12}$。

非常简单

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr itn oo = 100004;
itn n;
int pri[oo],cnt;
bool vis[oo];
int use[oo],is[oo],top;
int out = 1;
__inline int qpow(itn a,int b){itn res=1;while(b){if (b&1)res*=a;a*=a;b>>=1;}return res;}
main(void){//fre();cin.tie(0)->sync_with_stdio(0);cin >> n;for (itn i=2;i<oo-5;i++){if (!vis[i]) pri[++cnt] = i;for (int j=1;j<=cnt&&pri[j]*i<oo-5;j++){vis[i*pri[j]] = 1;if (i%pri[j]==0)break;}}//p_(pri,cnt,2);int i = 1;while (n&&i<=cnt){if (n%pri[i]==0){is[++top] = pri[i];while(n%is[top]==0){n/=is[top];use[top]++;}}i++;}for (itn i=1;i<=top;i++){if (use[i]>=2)break;if (i==top){cout << -1 << '\n';exit(0);}}for (int i=1;i<=top;i++){itn p = (use[i]+1)/2;out *= qpow(is[i],p);}cout << out << '\n';exit(0);
}

B. 华二

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

---

题目描述

$\text{Ayano}$ 喜欢 GCD。

现在她有一个长度为 $n$ 的数列 $A=(a_1,\cdots ,a_n)$，其中 $1\le a_i\le 9$。对于其中相邻的两项的 $a_i$ 和 $a_{i+1}$ ，满足 $gcd(a_i,a_{i+1})=1$ 时，$\text{Ayano}$ 可以通过一次操作交换 $a_i$ 和 $a_{i+1}$ $(1\le i\le n-1)$。

请你计算 $\text{Ayano}$ 可以通过这个操作得到多少种数列（包含原数列）$(\mathrm{mod}998244353)$。

输入格式

第一行一个数 $n$ ，表示数列的长度。

第二行 $n$ 个数，第 $i$ 个数表示 $a_i$。

输出格式

一行一个数表示答案。

样例输入 1

3
8 3 2

样例输出 1

3

样例输入 2

9
1 2 3 4 5 6 7 8 9

样例输出 2

3024

数据范围

• 对于 $30\%$ 的数据：$2\le n\le 10$；
• 对于另外 $10\%$ 的数据：$a_i\le 3$；
• 对于 $100\%$ 的数据：$2\le n\le 100000$，$1\le a_i\le 9$。

非常有意思的一道计数题，关键在于数量为9

我们通过公因数进行分类

分成2.3

发现6比较特殊，两个公因数都有，又发现同公因数之间相对位置不会改变，

我们考虑在中间排列计数即可

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long
#define int long long 
constexpr int oo = 1000006;
constexpr itn op = 1000000;
constexpr itn mod = 998244353;
__inline itn qpow(itn a,int b){itn res=1;while(b){if(b&1)res=(res*a)%mod;a=(a*a)%mod;b>>=1;}return res;}
int n;
int st[oo];itn fac[oo],ifac[oo];
int cnt1,cnt2,cnt3,cnt6,cnt5,cnt7;
main(void){//fre();cin.tie(nullptr)->ios::sync_with_stdio(false);cin >> n;for(int i=1;i<=n;i++)cin >> st[i];fac[0]=1;for(int i=1;i<=op;i++)fac[i]=fac[i-1]*i%mod;ifac[op]=qpow(fac[op],mod-2);for(int i=op;i>=1;i--)ifac[i-1]=ifac[i]*i%mod;itn out=1;for(int i=1;i<=n;i++){if(st[i]==1) cnt1++;else if(st[i]==5)cnt5++;else if(st[i]==7)cnt7++;else if(st[i]==2||st[i]==4||st[i]==8)cnt2++,cnt6++;else if(st[i]==3||st[i]==9)cnt3++,cnt6++;else if(st[i]==6){cnt6++;out=out*fac[cnt2+cnt3]%mod*ifac[cnt2]%mod*ifac[cnt3]%mod;cnt2=cnt3=0;}}out=out*fac[cnt2+cnt3]%mod*ifac[cnt2]%mod*ifac[cnt3]%mod;out=out*fac[cnt1+cnt6+cnt5+cnt7]%mod*ifac[cnt1]%mod*ifac[cnt6]%mod*ifac[cnt5]%mod*ifac[cnt7]%mod;cout << out << '\n';exit (0);
}

C. 高爸

时间限制: 1 s   内存限制: 512 MB   测评类型: 传统型

---

$\text{Shintaro}$ 有 $n$ 条龙。 第 $i$ 条龙的力量值是 $x_i$。现在 $\text{Shintaro}$ 想与这些龙交朋友。

$\text{Shintaro}$ 会使用以下两种魔法来平衡龙的力量值（使某些龙的力量值相等），以免与他交朋友的龙互相打架。

强化魔法：消耗 $a$ 点 p，使某条龙的力量值增加1点。

弱化魔法：消耗 $b$ 点 p，使某条龙的力量值降低1点。

在第 $i$ 次,$\text{Shintaro}$ 想与前 $i$ 条龙交朋友$(1\le i\le n)$。我们有很多种使用魔法的方案，使前 $i$ 条龙力量值相等。请你找到消耗 mp 点数最小的方案，并输出 mp 点数。

输入格式

第一行三个数 $n$ $a$ $b$ ，表示龙的条数，强化魔法消耗的 $mp$ 点数，弱化魔法消耗的 $mp$ 点数。

第二行 $n$ 个数，第 $i$ 个数 $x_i$ 表示第 $i$ 条龙的力量值。

输出格式

共 $n$ 行，第 $i$ 行输出一个整数表示使前 $i$ 条龙力量值相等所需的最小 $mp$ 点数。

样例输入 1

5 3 2
5 1 4 2 3

样例输出 1

0
8
11
13
15

数据范围

• 对于 $50\%$ 的数据：$n\le 1000$；
• 对于另外 $20\%$ 的数据：$1\le x_i\le 100$；
• 对于 $100\%$ 的数据：$1\le n\le 100000$，$1\le a,b\le 10^4$，$1\le x_i\le 10^9$。

不难发现力量为其中一条龙时一定会最优，50%时考虑枚举那一条龙的权值

100%时，对前面加入的权值进行排序，考虑在之前的结束值左右移动，选择更优的，复杂度$O(nlogn)$

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define int long long 
#define itn long long 
constexpr int oo = 1e5+10;
constexpr int inf = 0x3f3f3f3f3f3f3f3f;
int n,st[oo],a,b;
int res;
priority_queue<int>ql;
priority_queue<int,vector<int>,greater<int>>qr;
main(void){//fre();cin.tie(0)->ios::sync_with_stdio(0);cin >> n >> a >> b;for(int i=1;i<=n;i++) cin>>st[i];int p=st[1],cnt=0;for(int i=1;i<=n;i++){if(st[i]<p){res+=(p-st[i])*a;ql.push(st[i]);}if(st[i]>p){res+=(st[i]-p)*b;qr.push(st[i]);}if(st[i]==p) cnt++;int ansl=inf,ansr=inf;if(ql.size()){int t=ql.top(),s=ql.size();ansl=res+(p-t)*(i-s)*b-(p-t)*s*a;}if(qr.size()){int t=qr.top(),s=qr.size();ansr=res+(t-p)*(i-s)*a-(t-p)*s*b;}if(ansr>=ansl){if(ansl<res){while(cnt--)qr.push(p);cnt=0; p=ql.top();while(ql.size()&&ql.top()==p)ql.pop(),cnt++;res=ansl;}}else{if(ansr<res){while(cnt--)ql.push(p);cnt=0;p=qr.top();while(qr.size()&&qr.top()==p)qr.pop(),cnt++;res=ansr;}}cout << res << "\n";}exit (0);
}

D. 金牌

时间限制: 2 s   内存限制: 512 MB   测评类型: 传统型

---

题目描述

$\text{Ayano}$ 有一棵 $n$ 个顶点的树（编号从 $1$ 到 $n$ )。 这棵树有 $n-1$ 条边，第 $i$ 条边连接顶点 $u_i$ 和顶点 $v_i$。 由于Ayano$\text{Ayano}$ 非常喜欢这棵树，树上的每条路径都被赋予了价值。具体地，这棵树上长度为 $d$ 的简单路径的价值是 $2^d$。

现在 $\text{Ayano}$ 对你发出了 $q$ 次询问，每次给出两个正整数 $x,y$ ，请你回答所有通过顶点 $x$ 和 $y$ 的简单路径的价值之和 $\mathrm{mod}998244353$。

注：简单路径是指路径上的各顶点均不互相重复的路径，路径的长度是指一条路径经过的边的条数。

输入格式

第一行一个数 $n$ ，表示顶点个数。

接下来 $n-1$ 行，其中第 $i$ 行两个数 $u_i,v_i$ 用于描述第 $i$ 条边。

接下来一行一个数 $q$ ，表示询问次数。

接下来 $q$ 行，其中第 $i$ 行两个数 $x_i,y_i$ 用于描述第 i$i$ 个询问。

输出格式

共 $q$ 行，第$i$ 行表示第 $i$ 次询问的答案。

样例输入1

5
1 2
2 3
2 4
4 5
3
1 3
2 3
3 4

样例输出1

4
18
12

数据范围

• 对于 $20\%$ 的数据，$n,q\le 1000$；
• 对于 $50\%$ 的数据，$n,q\le 100000$；
• 对于 $100\%$ 的数据，$n,q\le 1000000$，$1\le u_i,v_i,x_i,y_i\le n$，$x_i\ne y_i$。

提示：本题数据量较大，建议使用快速的读写方式。

考虑把一条路径对答案的贡献分成三部分，$x$ 的子树内（$y$ 为根时），$y$ 的子树内（$x$ 为根时），$x$ 和 $y$ 之间的路径。那么相同部分可以相加，最后乘起来就行了。对于前两部分可以换根或者预处理讨论，第三部分需要 Tarjan 求 LCA。

复杂度$O(n)$。

//2024.9.14
//by white_ice
#include<bits/stdc++.h>
//#include"../../../need.cpp"
using namespace std;
#define itn long long 
#define int long long 
constexpr int oo = 1000010;
constexpr itn op = 2000010;
constexpr int mod = 998244353;
int n,q;int head[oo],st[op],ne[op];
itn mi[oo],idx,dis[oo],sz[oo];
int tp[oo],son[oo],fa[oo];
int f[oo],g[oo],dfn[oo],rdfn[oo],tim;
void add(int u,int v){st[idx]=v,ne[idx]=head[u],head[u]=idx++;}
void getdis(int x,int pr){dis[x]=dis[pr]+1,sz[x]=f[x]=1;for(int i=head[x],y;~i;i=ne[i])if((y=st[i])^pr){fa[y]=x,getdis(y,x),sz[x]+=sz[y],f[x]=(f[x]+2*f[y])%mod;if(sz[y]>sz[son[x]]) son[x]=y;}
}
void gettop(int x,int c){tp[x]=c,rdfn[dfn[x]=++tim]=x;if(!son[x]) return;g[son[x]]=(2*g[x]+3*(mod-f[son[x]]))%mod,gettop(son[x],c);for(int i=head[x],y;~i;i=ne[i])if((y=st[i])!=fa[x]&&y!=son[x])g[y]=(2*g[x]+3*(mod-f[y]))%mod,gettop(y,y);
}
int lca(int u,int v){while(tp[u]^tp[v])if(dis[tp[u]]>=dis[tp[v]]) u=fa[tp[u]];else v=fa[tp[v]];return dis[u]>=dis[v]?v:u;
}
int kth(int u,int k){while(dis[u]-k<dis[tp[u]]) k-=dis[u]-dis[fa[tp[u]]],u=fa[tp[u]];return rdfn[dfn[u]-k];
}
main(void){//fre();cin.tie(0)->sync_with_stdio(0);cin >> n;mi[0]=1;memset(head,-1,sizeof(head));for(int i=1,u,v;i<n;++i){cin >> u >>v ;add(u,v),add(v,u);mi[i]=mi[i-1]*2%mod;}getdis(1,0);g[1]=f[1],gettop(1,1);cin >> q;for(int i=1,u,v,t;i<=q;++i){cin >> u >> v;t=lca(u,v);if(t==v) u^=v^=u^=v;if(t==u) cout << ((g[u]+2*(mod-f[kth(v,dis[v]-dis[u]-1)]))*f[v]%mod*mi[dis[v]-dis[u]]%mod) << '\n';else cout << (f[u]*f[v]%mod*mi[dis[u]+dis[v]-2*dis[t]]%mod) << '\n'; }return 0;
}