Editorial for Số huyền bí

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này

Code mẫu của flashmt

const k=20122007;
var a:array[0..32] of int64;
d:array[0..32] of byte;
uoc:array[1..10000] of int64;
n,num:int64;
re:int64;

procedure rf;
begin
end;

procedure init;
var i:byte; j:longint;
begin
a[0]:=1; a[1]:=3;
for i:=2 to 32 do
a[i]:=(a[i-1]*a[i-1]) mod k;
num:=0;
for j:=1 to trunc(sqrt(n)) do
if n mod j = 0 then
begin
num:=num+2;
uoc[num-1]:=j;
uoc[num]:=n div j;
end;
if sqr(trunc(sqrt(n)))=n then dec(num);
end;

function calc(m:int64):int64;
var i:byte; res:int64;
begin
fillchar(d,sizeof(d),0);
i:=1;
while m>0 do
begin
d[i]:=m mod 2;
m:=m div 2;
inc(i);
end;
res:=1;
for i:=0 to 32 do
if d[i]=1 then res:=(res*a[i]) mod k;
calc:=res-1;
end;

procedure pr;
var i:longint;
begin
init;
re:=1;
for i:=1 to num do
re:=(re*calc(uoc[i])) mod k;
end;

procedure wf;
begin
write(re mod k);
end;

begin
rf;
pr;
wf;
end.


Code mẫu của happyboy99x

#include <algorithm>
#include <bitset>
#include <cctype>
#include <cfloat>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <deque>
#include <functional>
#include <iostream>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <utility>
#include <vector>
using namespace std;

typedef pair<int, int> ii;
typedef vector<ii> vii;
typedef vector<vii> vvii;
typedef vector<int> vi;
typedef vector<vi> vvi;

#define sz(a) int((a).size())
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define all(c) (c).begin(), (c).end()
#define tr(c,i) for(typeof((c).begin()) i = (c).begin(), _e = (c).end(); it != _e; ++it)
#define present(c,x) ((c).find(x) != (c).end())
#define cpresent(c,x) (find(all(c),x) != (c).end())
#define rep(i,n) for(int i = 0, _n = (n); i < _n; ++i)
#define repd(i,n) for(int i = (n)-1; i >= 0; --i )
#define fo(i,a,b) for(int i = (a), _b = (b); i <= _b; ++i)
#define fod(i,a,b) for(int i = (a), _b = (b); i >= _b; --i)

#define INF 1000000000
#define N
#define MOD 20122007

map<int, long long> mymap;

long long mod( int d ) {
if( d == 0 ) return 1;
if( d == 1 ) return 3;
if(present(mymap, d)) return mymap[d];
return mymap[d] = ((mod(d/2)%MOD * mod(d-d/2)%MOD) % MOD);
}

int main() {
int n; scanf( "%d", &n );
int k = (int) sqrt(n);
long long res = 1;
if( k * k == n ) res = mod(k--)-1;
fo(i,1,k) if( n % i == 0 ) {
res = (((res * (mod(i)-1)) % MOD) * (mod(n/i)-1)) % MOD;
}
cout << res << endl;
return 0;
}


program mystery;
uses    math;
const   loop=84420;
base=20122007;
var     pow:array[0..100000] of longint;
n,i,k:longint;
res:int64;
begin
i:=0;
pow[0]:=1;
for i:=1 to loop do
pow[i]:=(pow[i-1]*3) mod base;
res:=1;
for i:=1 to trunc(sqrt(n)) do
begin
if n mod i = 0 then
begin
res:=(res*(pow[i mod loop]-1)) mod base;
k:=n div i;
if k<>i then
res:=(res*(pow[k mod loop]-1)) mod base;
end;
end;
write(res);
end.


Code mẫu của RR

const
base=20122007;
var
res,a,i,gh,tmp:longint;

function lt3(k:longint):longint;
var
mid:longint;
begin
if k=0 then exit(1);
if k=1 then exit(3);
mid:=lt3(k shr 1);
mid:=(int64(mid)*mid) mod base;
if k and 1=1 then mid:=(mid*3) mod base;
exit(mid);
end;

begin
gh:=trunc(sqrt(a)); res:=1;
for i:=1 to gh do
if a mod i=0 then
begin
tmp:=lt3(i); dec(tmp); if tmp<0 then tmp:=base-1;
res:=(int64(res)*tmp) mod base;
if i*i<>a then
begin
tmp:=lt3(a div i); dec(tmp); if tmp<0 then tmp:=base-1;
res:=(int64(res)*tmp) mod base;
end;
end;
writeln(res);
end.


Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
long long f(long long n)
{
if(n<=15)
return (long long)(pow(3,n));
else if(n%2==0)
return (long long)(pow(f(n/2),2))%20122007;
else return (long long)(3*f(n-1))%20122007;
}
main()
{
long long N,KQ=1;
scanf("%lld",&N);
for(long long i=1;i<=sqrt(N);i++)
{
if(i*i==N)
KQ=KQ*(f(i)-1)%20122007;
else if(N%i==0)
{
KQ=KQ*(f(i)-1)%20122007;
KQ=KQ*(f(N/i)-1)%20122007;
}
}
printf("%lld",KQ);
//getch();
}


Code mẫu của ll931110

Program MYSTERY;
Const
input  = '';
output = '';
num    = 20122007;
con    = 2279340;
Var
a,n: longint;
k: array[1..100000] of longint;
s: int64;

Procedure init;
Var
f: text;
Begin
Assign(f, input);
Reset(f);
Close(f);
End;

Procedure gens;
Var
i: longint;
Begin
n:= 0;

For i:= 1 to trunc(sqrt(a)) do
if a mod i = 0 then
Begin
inc(n);
k[n]:= i mod con;

If i * i <> a then
Begin
inc(n);
k[n]:= (a div i) mod con;
End;
End;
End;

Function power(x,p,q: longint): int64;
Var
u: int64;
Begin
If p = 0 then exit(1);

u:= power(x,p div 2,q);
If odd(p) then power:= (u * u * x) mod q
else power:= (u * u) mod q;
End;

Procedure solve;
Var
f: text;
i,j: longint;
Begin
Assign(f, output);
Rewrite(f);

s:= 1;
For i:= 1 to n do
s:= s * (power(3,k[i],num) - 1) mod num;

Writeln(f, s);
Close(f);
End;

Begin
init;
gens;
solve;
End.


Code mẫu của skyvn97

#include<bits/stdc++.h>
const int mod=20122007;
int pw(int a,int b) {
int res=1;
int mul=a;
while (b>0) {
if (b&1) res=1LL*res*mul%mod;
mul=1LL*mul*mul%mod;
b>>=1;
}
return (res-1);
}
int main(void) {
int n;
scanf("%d",&n);
int pro=1;
for (int i=1;i*i<=n;i=i+1) if (n%i==0) {
pro=1LL*pro*pw(3,i)%mod;
if (i*i<n) pro=1LL*pro*pw(3,n/i)%mod;
}
printf("%d",pro);
return 0;
}