Editorial for Câu đố của thần đèn
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
#include <iostream> #include <algorithm> using namespace std; const int base = 1000000007; char d[5000100]; long long ans=1; long long countDivisor(int n,int i) { long long p=i,res=0; while (p<=n) res+=n/p, p*=i; return res; } long long power(long long x,long long y) { if (!y) return 1; long long res=power(x,y/2); res=res*res%base; if (y%2) res=res*x%base; return res; } int main() { int n; cin >> n; for (int i=2;i*i*2<=n;i++) if (!d[i]) for (int j=i*i;j*2<=n;j+=i) d[j]=1; for (int i=2;i*2<=n;i++) if (!d[i]) ans=ans*power(i,countDivisor(n,i)/2*2)%base; cout << ans << endl; }
Code mẫu của ladpro98
program c11genie; uses math; const fi=''; maxN=trunc(1e7)+1; base=trunc(1e9)+7; var sieve:array[1..maxN] of boolean; prime,a:array[1..maxN] of longint; res:int64; n,d,m:longint; procedure input; var inp:text; begin assign(inp,fi); reset(inp); readln(inp,n); close(inp); end; procedure init; var i,j:longint; begin fillchar(sieve,sizeof(sieve),true); m:=n; for i:=2 to m do if sieve[i] then begin j:=i+i; while j<=m do begin sieve[j]:=false; inc(j,i); end; end; for i:=2 to m do if sieve[i] then begin inc(d); prime[d]:=i; end; res:=1; end; function powmod(i,k:longint):longint; var m:longint; t:int64; begin if k=0 then exit(1); if k=1 then exit(i); m:=k shr 1; t:=powmod(i,m); if not odd(k) then exit((t*t) mod base); exit((((t*t) mod base)*i) mod base); end; procedure process; var i,k,x:longint; j:int64; begin for i:=1 to d do begin j:=prime[i]; while j<=n do begin inc(a[i],n div j); j:=j*prime[i]; end; if a[i]=1 then begin d:=i-1; break; end; end; for i:=1 to d do begin x:=powmod(prime[i],a[i] -(a[i] and 1)); res:=(res*x) mod base; end; end; begin input; init; process; write(res); end.
Code mẫu của RR
#include <sstream> #include <iomanip> #include <iostream> #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <algorithm> #include <vector> #include <set> #include <map> #include <stack> #include <queue> #include <string> #include <deque> #include <complex> #define FOR(i,a,b) for(int i=(a),_b=(b); i<=_b; i++) #define FORD(i,a,b) for(int i=(a),_b=(b); i>=_b; i--) #define REP(i,a) for(int i=0,_a=(a); i<_a; i++) #define FORN(i,a,b) for(int i=(a),_b=(b);i<_b;i++) #define DOWN(i,a,b) for(int i=a,_b=(b);i>=_b;i--) #define SET(a,v) memset(a,v,sizeof(a)) #define sqr(x) ((x)*(x)) #define ll long long #define F first #define S second #define PB push_back #define MP make_pair #define DEBUG(x) cout << #x << " = "; cout << x << endl; #define PR(a,n) cout << #a << " = "; FOR(_,1,n) cout << a[_] << ' '; cout << endl; #define PR0(a,n) cout << #a << " = "; REP(_,n) cout << a[_] << ' '; cout << endl; using namespace std; //Buffer reading int INP,AM,REACHEOF; #define BUFSIZE (1<<12) char BUF[BUFSIZE+1], *inp=BUF; #define GETCHAR(INP) { \ if(!*inp) { \ if (REACHEOF) return 0;\ memset(BUF,0,sizeof BUF);\ int inpzzz = fread(BUF,1,BUFSIZE,stdin);\ if (inpzzz != BUFSIZE) REACHEOF = true;\ inp=BUF; \ } \ INP=*inp++; \ } #define DIG(a) (((a)>='0')&&((a)<='9')) #define GN(j) { \ AM=0;\ GETCHAR(INP); while(!DIG(INP) && INP!='-') GETCHAR(INP);\ if (INP=='-') {AM=1;GETCHAR(INP);} \ j=INP-'0'; GETCHAR(INP); \ while(DIG(INP)){j=10*j+(INP-'0');GETCHAR(INP);} \ if (AM) j=-j;\ } //End of buffer reading const long double PI = acos((long double) -1.0); int n; bool sieve[10111000]; void init() { FOR(i,2,10000) if (!sieve[i]) { int j = i*i; while (j <= n) { sieve[j] = true; j += i; } } } int get(int p, int n) { if (p > n) return 0; return get(p, n/p) + n/p; } const long long MOD = 1000000007; long long power(int p, int k) { if (k == 0) return 1; if (k == 1) return p; long long mid = power(p, k >> 1); mid = (mid * mid) % MOD; if (k & 1) return (mid * p) % MOD; else return mid; } int main() { scanf("%d", &n); init(); long long res = 1; FOR(i,2,n) if (!sieve[i]) { int p = get(i, n); if (p & 1) --p; res = (res * power(i, p)) % MOD; } cout << res << endl; return 0; }
Code mẫu của hieult
#include <set> #include <map> #include <list> #include <cmath> #include <queue> #include <stack> #include <cstdio> #include <string> #include <vector> #include <cstdlib> #include <cstring> #include <sstream> #include <iomanip> #include <iostream> #include <algorithm> #include <ctime> #include <deque> #include <bitset> #include <cctype> #include <utility> #include <cassert> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned int ui; typedef unsigned long long ull; #define Rep(i,n) for(int i = 0; i < (n); ++i) #define Repd(i,n) for(int i = (n)-1; i >= 0; --i) #define For(i,a,b) for(int i = (a); i <= (b); ++i) #define Ford(i,a,b) for(int i = (a); i >= (b); --i) #define Fit(i,v) for(__typeof((v).begin()) i = (v).begin(); i != (v).end(); ++i) #define Fitd(i,v) for(__typeof((v).rbegin()) i = (v).rbegin(); i != (v).rend(); ++i) #define mp make_pair #define pb push_back #define fi first #define se second #define sz(a) ((int)(a).size()) #define all(a) (a).begin(), (a).end() #define ms(a,x) memset(a, x, sizeof(a)) template<class F, class T> T convert(F a, int p = -1) { stringstream ss; if (p >= 0) ss << fixed << setprecision(p); ss << a; T r; ss >> r; return r; } template<class T> T gcd(T a, T b) { T r; while (b != 0) { r = a % b; a = b; b = r; } return a; } template<class T> T lcm(T a, T b) { return a / gcd(a, b) * b; } template<class T> T sqr(T x) { return x * x; } template<class T> T cube(T x) { return x * x * x; } template<class T> int getbit(T s, int i) { return (s >> i) & 1; } template<class T> T onbit(T s, int i) { return s | (T(1) << i); } template<class T> T offbit(T s, int i) { return s & (~(T(1) << i)); } template<class T> int cntbit(T s) { return s == 0 ? 0 : cntbit(s >> 1) + (s & 1); } typedef pair<int, int> II; const double PI = acos(-1.0); const double eps = 1e-3; const int dr[] = { -1, 0, +1, 0 }; const int dc[] = { 0, +1, 0, -1 }; const int inf = (int) 1e9 + 5; const ll linf = (ll) 1e16 + 5; const ll mod = (ll) 1e9 + 7; #define maxn 10000005 int N; bool isprime[maxn]; void init(){ ms(isprime, 1); isprime[1] = 0; for(int i = 2; i * i <= maxn; i++) if(isprime[i]){ for(int j = i * i; j < maxn; j += i) isprime[j] = 0; } } ll cal(ll A, ll x){ ll res = 0; while(A > 0){ A /= x; res += A; } return res; } ll mul(ll A, ll x){ if(x == 0) return 1; if(x & 1) return A * mul(A, x - 1) % mod; ll t = mul(A, x >> 1); return (t * t) % mod; } ll n; int main() { // freopen("in.txt", "r", stdin); init(); cin >> n; ll res = 1; For(i, 2, n) if(isprime[i]){ ll t = cal(n, i); if(t & 1) t--; res = (res * mul(i, t)) % mod; } cout << res << endl; return 0; }
Comments