原题链接
题意
给一个素数 nnn ，问 i=[1,n?1]i = [1 , n - 1]i=[1,n?1]，做几次操作 iii 可以变成1，操作是 i=nmodii = n\ mod\ ii=n mod i，且它本身也算一次操作，用所有i变成1的总次数除以 n?1n - 1n?1，结果保留十位小数。
思路
一开始虽然也有想到要记下来，因为一些数是重复出现的，但是没有想到要用记忆化搜索，因为一直以来都不太会写记忆化搜索。
后来去把记忆化搜索重学了一遍，发现这题其实真的非常简单，用记忆化搜索补过了，可还是不太理解为什么之前写的不过。。
详情看代码注释吧，挺好想的。
代码
#include<bits/stdc++.h>
using namespace std;
int ans[2000050];int f(int x, int p)
{
int v = 1;if (ans[x] != -1) //如果这一步之前已经被算过{
return ans[x]; //就直接返回之前已经算好的结果}if (x == 1)//如果找到1，也就是已经除到底了，最后一步操作{
ans[x] = v; //那么就给这一步操作赋值为1，其实我感觉这个地方只会来1次，因为只有1个1，只要1被赋值后，后面的在上一步的时候就会被返回了，因为1已经被记忆化了return v; //返回1其实}else{
v += f(p % x, p); //做操作，并接受返回值ans[x] = v; //返回的是多少，说明它做了几次操作，那么这一步x的操作数就是返回值，v+=是因为还要算上它本身return ans[x];//返回结果}
}int main()
{
int t;cin >> t; //T组数据while (t -- ){
int n;cin >> n;int sum = 0;memset(ans, -1, sizeof ans);for (int i = 1; i <= n - 1; i ++ ){
sum += f(i, n); //计算总数}// 强制类型转换printf("%.10f\n", (double)sum / (double)(n - 1));}return 0;
}总结
去年江苏省赛的签到题，没想到就用到了记忆化搜索，我还不太会写，明天就是今年的江苏省赛了，真害怕爆零。
但是无论结果如何，都不会气馁，坚持，就是胜利！