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
     read(n);
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;
}

Code mẫu của ladpro98

program mystery;
uses    math;
const   loop=84420;
        base=20122007;
var     pow:array[0..100000] of longint;
        n,i,k:longint;
        res:int64;
begin
        readln(n);
        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
  read(a);
  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);
                        Readln(f, a);
                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;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.