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.
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