Wannafly Winter Camp 2020 Day 5G Cryptographically Secure Pseudorandom Number Generator

多组数据，给定质数 \(p\) ，求所有 \(x\) 使得 \(f(x)=\min_{k=2}^x f(k)\) ，其中 \(f(x)=x^{-1}\)

所有 \(p\) 在 \([1,10^9]\) 中均匀选取

Solution

显然逆元序列有对称关系

于是枚举到根号，后面一半对称输出即可

我为什么被这个题卡了一个小时

一开始枚举边界写的是 \(\sqrt p\) 怎么都过不去

后来发现我可能是个沙茶

#include <bits/stdc++.h>

using namespace std;

#define int long long

int a[1000005],p,t;

signed main() {

    ios::sync_with_stdio(false);

    cin>>t;

    while(t--) {

        cin>>p;

        vector <pair<int,int> > v;

        int lim=sqrt(p);

        a[1]=1;

        int mx=1e9,pos=1;

        for(int i=2;i<=p;i++) {

            a[i]=-(p/i)*a[p%i],

            a[i]=(a[i]%p+p)%p;

            if(i>=a[i]) break;

            mx=min(mx,a[i]);

            if(mx==a[i]) {

                if(i<a[i])

                    v.push_back(make_pair(i,a[i]));

            }

        }

        int flag=0;

        if(sqrt(p+1) == (int)sqrt(p+1)) flag=1;

        cout<<2*v.size()+flag<<endl;

        for(int i=0;i<v.size();i++) cout<<v[i].first<<" "<<v[i].second<<endl;

        if(flag) cout<<(int)sqrt(p+1)<<" "<<(int)sqrt(p+1)<<endl;

        for(int i=v.size()-1;i>=0;--i) cout<<v[i].second<<" "<<v[i].first<<endl;

    }

}

巴特西

Wannafly Winter Camp 2020 Day 5G Cryptographically Secure Pseudorandom Number Generator - 分块

Solution

最新文章

热门文章