QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#374847	#3051. Identity Function	SolitaryDream^#	WA	1ms	3836kb	C++17	1.6kb	2024-04-02 18:49:12	2024-04-02 18:49:13

Judging History

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

[2024-04-02 18:49:13]
评测

测评结果：WA
用时：1ms
内存：3836kb

查看

[2024-04-02 18:49:12]
提交

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;
}

signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    int n;
    cin>>n;
    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;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)
    //     {
    //         cout<<k<<endl;
    //         break;
    //     }
    // }
    vector<int> ans;
    for(int i=1;i*i<=w;i++)
        if(w%i==0)
        {
            if(qpow(n,i,pn)==1%pn)
                ans.push_back(i);
            if(qpow(n,w/i,pn)==1%pn)
                ans.push_back(w/i);
            if(qpow(n,i+w,pn)==1%pn)
                ans.push_back(i+w);
            if(qpow(n,w/i+w,pn)==1%pn)
                ans.push_back(w/i+w);
        }
    if(ans.size())
        cout<<*min_element(ans.begin(),ans.end())<<"\n";
    else
        cout<<"-1\n";
}

Source code, Language: C++17

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 1ms

memory: 3540kb

input:

output:

result:

ok single line: '1'

Test #2:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

-1

result:

ok single line: '-1'

Test #3:

score: 0

Accepted

time: 1ms

memory: 3536kb

input:

output:

result:

ok single line: '2'

Test #4:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

result:

ok single line: '1'

Test #5:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

output:

result:

ok single line: '1'

Test #6:

score: 0

Accepted

time: 0ms

memory: 3608kb

input:

output:

-1

result:

ok single line: '-1'

Test #7:

score: 0

Accepted

time: 0ms

memory: 3836kb

input:

output:

result:

ok single line: '1'

Test #8:

score: 0

Accepted

time: 0ms

memory: 3756kb

input:

output:

-1

result:

ok single line: '-1'

Test #9:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

result:

ok single line: '1'

Test #10:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

-1

result:

ok single line: '-1'

Test #11:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

output:

-1

result:

ok single line: '-1'

Test #12:

score: 0

Accepted

time: 0ms

memory: 3548kb

input:

output:

-1

result:

ok single line: '-1'

Test #13:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

output:

result:

ok single line: '1'

Test #14:

score: 0

Accepted

time: 0ms

memory: 3580kb

input:

output:

-1

result:

ok single line: '-1'

Test #15:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

output:

result:

ok single line: '1'

Test #16:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

output:

-1

result:

ok single line: '-1'

Test #17:

score: 0

Accepted

time: 0ms

memory: 3760kb

input:

output:

result:

ok single line: '2'

Test #18:

score: 0

Accepted

time: 0ms

memory: 3816kb

input:

output:

-1

result:

ok single line: '-1'

Test #19:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

output:

result:

ok single line: '1'

Test #20:

score: 0

Accepted

time: 0ms

memory: 3828kb

input:

output:

-1

result:

ok single line: '-1'

Test #21:

score: 0

Accepted

time: 1ms

memory: 3536kb

input:

output:

result:

ok single line: '1'

Test #22:

score: 0

Accepted

time: 0ms

memory: 3780kb

input:

output:

-1

result:

ok single line: '-1'

Test #23:

score: 0

Accepted

time: 0ms

memory: 3544kb

input:

output:

-1

result:

ok single line: '-1'

Test #24:

score: 0

Accepted

time: 1ms

memory: 3540kb

input:

140232429

output:

-1

result:

ok single line: '-1'

Test #25:

score: 0

Accepted

time: 0ms

memory: 3592kb

input:

21672344

output:

-1

result:

ok single line: '-1'

Test #26:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

229029120

output:

-1

result:

ok single line: '-1'

Test #27:

score: 0

Accepted

time: 0ms

memory: 3624kb

input:

511616301

output:

-1

result:

ok single line: '-1'

Test #28:

score: 0

Accepted

time: 0ms

memory: 3564kb

input:

output:

-1

result:

ok single line: '-1'

Test #29:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

output:

-1

result:

ok single line: '-1'

Test #30:

score: 0

Accepted

time: 1ms

memory: 3628kb

input:

256102461

output:

-1

result:

ok single line: '-1'

Test #31:

score: 0

Accepted

time: 1ms

memory: 3544kb

input:

477992350

output:

-1

result:

ok single line: '-1'

Test #32:

score: 0

Accepted

time: 1ms

memory: 3540kb

input:

28628975

output:

-1

result:

ok single line: '-1'

Test #33:

score: 0

Accepted

time: 0ms

memory: 3540kb

input:

324852814

output:

-1

result:

ok single line: '-1'

Test #34:

score: 0

Accepted

time: 1ms

memory: 3592kb

input:

output:

-1

result:

ok single line: '-1'

Test #35:

score: 0

Accepted

time: 1ms

memory: 3580kb

input:

59900148

output:

-1

result:

ok single line: '-1'

Test #36:

score: 0

Accepted

time: 1ms

memory: 3488kb

input:

53150292

output:

-1

result:

ok single line: '-1'

Test #37:

score: 0

Accepted

time: 0ms

memory: 3576kb

input:

194354668

output:

-1

result:

ok single line: '-1'

Test #38:

score: 0

Accepted

time: 0ms

memory: 3584kb

input:

72185553

output:

-1

result:

ok single line: '-1'

Test #39:

score: 0

Accepted

time: 0ms

memory: 3568kb

input:

423042624

output:

-1

result:

ok single line: '-1'

Test #40:

score: 0

Accepted

time: 0ms

memory: 3524kb

input:

output:

-1

result:

ok single line: '-1'

Test #41:

score: 0

Accepted

time: 0ms

memory: 3536kb

input:

144315184

output:

-1

result:

ok single line: '-1'

Test #42:

score: 0

Accepted

time: 1ms

memory: 3828kb

input:

170662393

output:

-1

result:

ok single line: '-1'

Test #43:

score: 0

Accepted

time: 1ms

memory: 3584kb

input:

output:

-1

result:

ok single line: '-1'

Test #44:

score: 0

Accepted

time: 0ms

memory: 3764kb

input:

429865917

output:

-1

result:

ok single line: '-1'

Test #45:

score: 0

Accepted

time: 1ms

memory: 3832kb

input:

119075974

output:

-1

result:

ok single line: '-1'

Test #46:

score: -100

Wrong Answer

time: 0ms

memory: 3788kb

input:

82251853

output:

result:

wrong answer 1st lines differ - expected: '5040', found: '20160'