QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#374896	#3051. Identity Function	SolitaryDream^#	AC ✓	344ms	3828kb	C++17	2.2kb	2024-04-02 19:21:11	2024-04-02 19:21:12

Judging History

你现在查看的是最新测评结果

[2024-04-02 19:21:12]
评测

测评结果：AC
用时：344ms
内存：3828kb

查看

[2024-04-02 19:21:11]
提交

answer

#include<bits/stdc++.h>
using namespace std;

#define int long long

const int N=1e5+1e3+7;

int phi(int x)
{
    int ans=x;
    for(int i=2;i*i<=x;i++)
        if(x%i==0)
        {
            ans=ans/i*(i-1);
            while(x%i==0)
                x/=i;
        }
    if(x!=1)
        ans=ans/x*(x-1);
    return ans;
}

int qpow(int a,int b,int P)
{
    int ret=1;
    while(b)
    {
        if(b&1)
            ret=ret*a%P;
        b>>=1;
        a=a*a%P;
    }
    return ret%P;
}

mt19937 rng(time(0));

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;

    cin>>n;
    // for(int n=2;n<=100;n++)
    {
        // int ans2=-1;
        int w=phi(phi(n));
        int pn=phi(n);
        // for(int k=1;k<=n;k++)
        // {
        //     bool ok=1;
        //     for(int a=1;a<=n*2;a++)
        //     {
        //         int w=a;
        //         for(int j=1;j<=k;j++)
        //             w=qpow(w,n,n);
        //         if(w!=a%n)
        //         {
        //             ok=0;
        //             break;
        //         }
        //     }
        //     if(ok)
        //     {
        //         ans2=k;
        //         break;
        //     }
        // }
        int ans1=1e18;
        for(int i=1;i*i<=w;i++)
            if(w%i==0)
            {
                int ok=1;
                for(int t=1;t<=20000;t++)
                {
                    int x=rng()%n;
                    if(qpow(x,qpow(n,i,pn)+pn,n)!=x%n)
                    {
                        ok=0;
                        break;
                    }
                }
                if(ok)
                    ans1=min(ans1,i);

                    
                ok=1;
                for(int t=1;t<=20000;t++)
                {
                    int x=rng()%n;
                    if(qpow(x,qpow(n,w/i,pn)+pn,n)!=x%n)
                    {
                        ok=0;
                        break;
                    }
                }
                if(ok)
                    ans1=min(ans1,w/i);
            }
        if(ans1>w)
            ans1=-1;
        // if(ans1!=ans2)
        //     cerr<<n<<"\n";
        cout<<ans1<<"\n";
    }
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 2ms

memory: 3664kb

input:

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3688kb

input:

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0

Accepted

time: 3ms

memory: 3680kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 2ms

memory: 3680kb

input:

output:

result:

ok single line: '1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3776kb

input:

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 2ms

memory: 3824kb

input:

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 1ms

memory: 3664kb

input:

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 2ms

memory: 3780kb

input:

output:

result:

ok single line: '1'

Test #10:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3768kb

input:

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0

Accepted

time: 4ms

memory: 3656kb

input:

output:

result:

ok single line: '1'

Test #14:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0

Accepted

time: 4ms

memory: 3820kb

input:

output:

result:

ok single line: '1'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

result:

ok single line: '2'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3784kb

input:

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0

Accepted

time: 4ms

memory: 3628kb

input:

output:

result:

ok single line: '1'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0

Accepted

time: 2ms

memory: 3668kb

input:

output:

result:

ok single line: '1'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3820kb

input:

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3824kb

input:

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

140232429

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0

Accepted

time: 1ms

memory: 3784kb

input:

21672344

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

229029120

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

511616301

output:

-1

result:

ok single line: '-1'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

-1

result:

ok single line: '-1'

Test #29:

score: 0

Accepted

time: 0ms

memory: 3684kb

input:

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3692kb

input:

256102461

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0

Accepted

time: 0ms

memory: 3772kb

input:

477992350

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0

Accepted

time: 1ms

memory: 3632kb

input:

28628975

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

324852814

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0

Accepted

time: 0ms

memory: 3680kb

input:

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0

Accepted

time: 0ms

memory: 3672kb

input:

59900148

output:

-1

result:

ok single line: '-1'

Test #36:

score: 0

Accepted

time: 1ms

memory: 3772kb

input:

53150292

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0

Accepted

time: 1ms

memory: 3824kb

input:

194354668

output:

-1

result:

ok single line: '-1'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

72185553

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0

Accepted

time: 0ms

memory: 3616kb

input:

423042624

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0

Accepted

time: 0ms

memory: 3732kb

input:

output:

-1

result:

ok single line: '-1'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

144315184

output:

-1

result:

ok single line: '-1'

Test #42:

score: 0

Accepted

time: 0ms

memory: 3676kb

input:

170662393

output:

-1

result:

ok single line: '-1'

Test #43:

score: 0

Accepted

time: 1ms

memory: 3744kb

input:

output:

-1

result:

ok single line: '-1'

Test #44:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

429865917

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0

Accepted

time: 1ms

memory: 3604kb

input:

119075974

output:

-1

result:

ok single line: '-1'

Test #46:

score: 0

Accepted

time: 203ms

memory: 3688kb

input:

82251853

output:

result:

ok single line: '5040'

Test #47:

score: 0

Accepted

time: 1ms

memory: 3640kb

input:

864042775

output:

-1

result:

ok single line: '-1'

Test #48:

score: 0

Accepted

time: 1ms

memory: 3688kb

input:

207433352

output:

-1

result:

ok single line: '-1'

Test #49:

score: 0

Accepted

time: 276ms

memory: 3768kb

input:

445441133

output:

result:

ok single line: '1'

Test #50:

score: 0

Accepted

time: 1ms

memory: 3668kb

input:

406486384

output:

-1

result:

ok single line: '-1'

Test #51:

score: 0

Accepted

time: 344ms

memory: 3684kb

input:

712020461

output:

result:

ok single line: '9560'

Test #52:

score: 0

Accepted

time: 1ms

memory: 3732kb

input:

71902918

output:

-1

result:

ok single line: '-1'

Test #53:

score: 0

Accepted

time: 1ms

memory: 3736kb

input:

423728046

output:

-1

result:

ok single line: '-1'

Test #54:

score: 0

Accepted

time: 42ms

memory: 3612kb

input:

680589143

output:

result:

ok single line: '5212012'

Test #55:

score: 0

Accepted

time: 1ms

memory: 3624kb

input:

832024203

output:

-1

result:

ok single line: '-1'

Test #56:

score: 0

Accepted

time: 1ms

memory: 3680kb

input:

298984850

output:

-1

result:

ok single line: '-1'

Test #57:

score: 0

Accepted

time: 1ms

memory: 3684kb

input:

807370504

output:

-1

result:

ok single line: '-1'

Test #58:

score: 0

Accepted

time: 1ms

memory: 3620kb

input:

207784112

output:

-1

result:

ok single line: '-1'

Test #59:

score: 0

Accepted

time: 1ms

memory: 3672kb

input:

148371537

output:

-1

result:

ok single line: '-1'

Test #60:

score: 0

Accepted

time: 30ms

memory: 3664kb

input:

output:

result:

ok single line: '149754'

Test #61:

score: 0

Accepted

time: 0ms

memory: 3740kb

input:

263272770

output:

-1

result:

ok single line: '-1'

Test #62:

score: 0

Accepted

time: 1ms

memory: 3784kb

input:

395241442

output:

-1

result:

ok single line: '-1'

Test #63:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

211961534

output:

-1

result:

ok single line: '-1'

Test #64:

score: 0

Accepted

time: 0ms

memory: 3744kb

input:

output:

-1

result:

ok single line: '-1'

Test #65:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

187763131

output:

-1

result:

ok single line: '-1'

Test #66:

score: 0

Accepted

time: 0ms

memory: 3628kb

input:

output:

-1

result:

ok single line: '-1'

Test #67:

score: 0

Accepted

time: 0ms

memory: 3668kb

input:

output:

-1

result:

ok single line: '-1'

Test #68:

score: 0

Accepted

time: 1ms

memory: 3720kb

input:

998977951

output:

-1

result:

ok single line: '-1'

Test #69:

score: 0

Accepted

time: 1ms

memory: 3784kb

input:

output:

-1

result:

ok single line: '-1'

Test #70:

score: 0

Accepted

time: 0ms

memory: 3652kb

input:

output:

-1

result:

ok single line: '-1'

Test #71:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

output:

-1

result:

ok single line: '-1'

Test #72:

score: 0

Accepted

time: 1ms

memory: 3780kb

input:

185444911

output:

-1

result:

ok single line: '-1'

Test #73:

score: 0

Accepted

time: 1ms

memory: 3616kb

input:

99214741

output:

-1

result:

ok single line: '-1'

Test #74:

score: 0

Accepted

time: 14ms

memory: 3684kb

input:

999997161

output:

166666192

result:

ok single line: '166666192'

Test #75:

score: 0

Accepted

time: 17ms

memory: 3620kb

input:

999998817

output:

166666468

result:

ok single line: '166666468'

Test #76:

score: 0

Accepted

time: 17ms

memory: 3692kb

input:

999991689

output:

166665280

result:

ok single line: '166665280'

Test #77:

score: 0

Accepted

time: 17ms

memory: 3824kb

input:

999984561

output:

166664092

result:

ok single line: '166664092'

Test #78:

score: 0

Accepted

time: 13ms

memory: 3772kb

input:

999984201

output:

166664032

result:

ok single line: '166664032'

Test #79:

score: 0

Accepted

time: 17ms

memory: 3688kb

input:

999962097

output:

166660348

result:

ok single line: '166660348'

Test #80:

score: 0

Accepted

time: 17ms

memory: 3780kb

input:

999953457

output:

166658908

result:

ok single line: '166658908'

Test #81:

score: 0

Accepted

time: 16ms

memory: 3684kb

input:

999952521

output:

166658752

result:

ok single line: '166658752'

Test #82:

score: 0

Accepted

time: 13ms

memory: 3616kb

input:

999952449

output:

166658740

result:

ok single line: '166658740'

Test #83:

score: 0

Accepted

time: 18ms

memory: 3772kb

input:

999947121

output:

166657852

result:

ok single line: '166657852'