Hướng dẫn giải của Số huyền bí
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
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; }
Bình luận