J - Just Multiplicative Inverse Gym - 102875J

題目：

題解：

給定一個x，求出F(1,x)+F(2,x)+…+F(x-1,x) 的和除以（x-1）
F(x,p)題目已經給出
我們觀察F()含義，再結合本題含義，本題并不是要求F(x,p)的值，而是求這個函數調用了 幾次
比如F(5,7)調用了3次，所以就貢獻了3，可以結合題目的Note理解
我們再看這個函數
返回了?p/x · F(p mod x, p) mod p，但是下一層遞歸只是p mod x，也就是其他的根本沒啥用，所以我們可以重新寫一下F函數，使得其最終返回的是遞歸的次數
結合題目范圍，用記憶化搜索優化

代碼：

#include<bits/stdc++.h> typedef long long ll; using namespace std; inline int read(){int s=0,w=1;char ch=getchar();while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();//s=(s<<3)+(s<<1)+(ch^48);return s*w; } const int maxn=1e6+9; int dp[maxn]; int ans=0; int F(int x,int p){if(dp[x])return ans=ans+dp[x];ans++;if(x<=1){// if(dp[x]==0)dp[x]=ans;return dp[x]=ans; }else {return dp[x]=F(p%x,p);} } int main() {int t;cin>>t;while(t--){int n;cin>>n;double sum=0;memset(dp,0,sizeof(dp));for(int i=1;i<n;i++){ans=0;sum+=1.0*F(i,n);}//cout<<sum<<endl;printf("%.10f\n",sum/((n-1)*1.0));// cout<<calu(n);}return 0; }

總結

以上是生活随笔為你收集整理的J - Just Multiplicative Inverse Gym - 102875J的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。