FCOI #11 官方题解
本帖最后由 sfqxx 于 2024-1-5 19:28 编辑https://fishc.com.cn/thread-237169-1-1.html 验题人题解，把我吊打了%%%
这里是 官方题解！
A-互关
一道简单模拟题，很快就能 AC ，就不讲了。
B-高斯记号
这里提供一个不一样的思路，出题人是用字符串做的调了好几次。
显然，第一种情况为将输入的数转换为整数（向下取整），第2种情况直接模拟
代码：
a,b=map(str,input().split())
if a=="1":
print(int(float(b)))
else:
c = list(b.split("."))
print("0."+c)
C 只因出现一次的数字
思路与验题人题解差不多，且本人代码可读性较差，不放了
D - 枪战
签到题放完了，我们从现在开始没有这么简单了。
考虑直接模拟，时间复杂度为 O(n2)，显然无法通过此题
考虑单调栈，与其不如求解一个人能干掉几个人，不如计算一个人能被几个人干掉，于是我们用栈模拟即可。
n=int(input())
b=0
st=[]
for i in range(n):
a=int(input())
while st and st[-1]<=a:
st.pop()
b+=len(st)
st.append(a)
print(b)
注意单调栈不要写错，我看 tommyu 好像就是拿了90pts就是因为这个原因（？
E 可恶的 zhangjinxuan
求证过程可以看验题人题解，出题人咕咕了
这道题可以用 Python 做，因为无需用高精度。
F -高斯记号
这道题可以套用 Python 中的eval
我们可以先将输入数据的高斯记号整理为正常表达式，然后注意精度。
（压轴题）G - 公因数
给定一个整数 $n$，你需要求出 $\sum\limits_{i=1}^n \gcd(i, n)$，其中 $\gcd(i, n)$ 表示 $i$ 和 $n$ 的最大公因数。
本题难点在于思路。
暴力可得 65 or 70 pts
正解：
我们先来看一张图：https://cdn.luogu.com.cn/upload/image_hosting/bc2pnqny.png
思路开始：注意到 gcd(i,n) 一定是 n 的约数，n 的约数却很少（最多为 d(n) 个）。考虑枚举 n 的约数（设为 d）, 再求出满足 gcd (i,n) = d 的 i 有多少个即可。考虑 i = i'd,那么必然有 i ⊥(n/d) 且 1 ≤ i ≤ (n/d)
(论坛打不出分数)。这样的i'(i)有 φ (n/d) 个。 对于 n 的每一个约数，也直接求出他的欧拉函数即可。
注意到 n 的约数 d 的约数 也一定是 n 的约数，所以在枚举 d 的约数 求解 φ(d) 时只要枚举之前求出的比 d 小的 n 的约数即可。时间复杂度为 O(√￣n + d2(n))。
#include<cstdio>
long long n;
long long f(){
long long ans=n; long long i;
for(i=2;i*i<=n;++i) if(n%i==0){
int b=0;
while(n%i==0) ++b,n/=i;
ans/=i;
ans*=b*i-b+i;
} if(n>1) ans/=n, ans*=n+n-1;
return ans;
}
int main(){
scanf("%lld",&n);
printf("%lld",f());
return 0;
}
官方题解没人啊{:10_256:} zhangjinxuan 发表于 2023-12-2 16:25
官方题解没人啊
是啊
页:
[1]