FJUT2019暑假周赛三部分题解

A本来想改到q<1e5，让你们预处理的，然后想了哈作为个逆元模板题吧= =，做不出来自行反思。

B贴个题面

因为只有一次机会，那么也就是两点分布期望E = p了，先说说大家的做法，先求出每个n的逆元保存，然后因为最大只会取到1e6，所以对0-1e6跑一遍每个数的倍数个数。复杂度O(N^1/3)，代码如下

 #include <iostream>

 using namespace std;

 typedef long long ll;

 const int maxn = ;

 ll sum[maxn+];

 ll sqr3(ll n){

     int l=,r=maxn+;

     while(l+<r){

         ll mid = (l+r)>>;

         if(mid*mid*mid>n)

             r=mid;

         else l=mid;

     }

     return l;

 }

 void exgcd(const ll a, const ll b, ll &g, ll &x, ll &y) {

     if (!b) g = a, x = , y = ;

     else exgcd(b, a % b, g, y, x), y -= x * (a / b);

 }

 ll inv(const ll num,const ll MOD) {

     ll g, x, y;

     exgcd(num, MOD, g, x, y);

     return ((x % MOD) + MOD) % MOD;

 }

 ll fast_mult(ll x,ll y,ll mod) {

     ll tmp=(x*y-(ll)((long double)x/mod*y+1.0e-8)*mod);

     return tmp< ? tmp+mod : tmp;

 }

 int main() {

     for(ll i=;i<=maxn;i++){

         sum[i]=sum[i-]+((i+)*(i+)*(i+)-)/i-(i*i*i-)/i;

     }

     int T;

     cin>>T;

     while(T--){

         ll n,mod;

         cin>>n>>mod;

         ll temp=sqr3(n);

         ll ans=sum[temp-]+n/temp-(temp*temp*temp-)/temp;

         ans=fast_mult(ans%mod,inv(n,mod)%mod,mod);

         cout<<ans<<endl;

     }

     return ;

 }

然后我的做法是

这里对每一步做一个解释 = =，大佬可以略过，[S]代表艾弗森约定，就是S为真则值为1，否则值为0。

对于第一个等号，就是求这些赢点的个数和。

对于第二个等号，用x来代表k的立方根的底。

对于第三个等号，第一个艾弗森约定应该不难理解，底肯定会小于等于原值。

对于第四个等号，这里第一个和式是处理边界，这里x=N的立方根的底（写错了，懒得重新改了）。这部就是把边界单独处理了。

对于第五个等号，讨论y的取值。

对于第六个等号，换底，然后是对y求和.

后面的同上，讨论取值求和。

最后就可以求得一个公式，因为要求立方根的底，建议用牛顿迭代求解。

最终的复杂度就是O(QlogN)。代码如下

 #include <bits/stdc++.h>

 using namespace std;

 typedef long long ll;

 int q;

 ll n,Mod,w;

 double newton(double x){

     double x1, x2;

     if (x == 0.0) return 0.0;

     x1 = x;

     x2 = (2.0 * x1 + x / (x1 * x1)) / 3.0;

     while (fabs((x2 - x1) / x1) >= 1E-) {

         x1 = x2;

         x2 = (2.0 * x1 + x / (x1 * x1)) / 3.0;

     }

     return x2;

 }

 void extgcd(ll a,ll b,ll& x,ll& y){

     if(!b){

         x = ;

         y = ;

         return ;

     }

     extgcd(b,a%b,y,x);

     y -= x*(a/b);

 }

 ll inverse(ll a,ll n){

     ll x,y;

     extgcd(a,n,x,y);

     return (x+n)%n;

 }

 ll qmul(ll a,ll b) {

     ll ans = ;

     while (b) {

         if (b&) {

             ans = (ans+a)%Mod;

         }

         a = (a+a)%Mod;

         b >>= ;

     }

     return ans;

 }

 void solve() {

     cin >> n >> Mod;

     ll k = newton(n);

     ll w = n/k - ;

     if (k&) {

         w += k*k/ + *k/ + ;

     } else {

         w += k/*k + k/*;

     }

     //cout << k << ' ' << w << endl;

     ll ans = qmul(w%Mod,inverse(n,Mod));

     cout << ans << endl;

 }

 int main() {

     ios_base::sync_with_stdio();

     cin >> q;

     while (q--) {

         solve();

     }

     return ;

 }

太伤心了= =，被离线算法吊打。

巴特西

FJUT2019暑假周赛三部分题解

最新文章

热门文章