Editorial for VM 10 Bài 08 - Tích


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 happyboy99x

#include<iostream>
#include<cmath>
#include<sstream>
#include<iomanip>
using namespace std;

const int MAX = 1e5;
const double EPS = 1e-9;
long double frt[MAX+1];

void init() {
    for(int i = 1; i <= MAX; ++i)
        frt[i] = frt[i-1] + log(i);
}

long double log(const string &p) {
    stringstream inp;
    if(p.size() < 14) {
        inp << p;
        long double d; inp >> d;
        return log(d);
    } else {
        inp << p.substr(0, 13);
        long double d; inp >> d;
        return log(d) + ((int) p.size() - 13) * log(10);
    }
}

int main() {
    ios::sync_with_stdio(false);
    init();
    string p; cin >> p;
    long double x = log(p);
    for(int i = 1, j = 1; i <= MAX; ++i) {
        while(j < MAX && frt[j] - frt[i-1] + EPS < x) ++j;
        if(abs(frt[j] - frt[i-1] - x) <= EPS) {
            cout << i << ' ' << j << endl;
            return 0;
        }
    }
    return 0;
}

Code mẫu của RR

{$MODE OBJFPC}
{$N+}
uses math;
var
  s: ansistring;
  x, y, i, n, k: integer;
  logs, logxy, u: double;

begin
  readln( s );
  n := length( s );
  k := min( n, 20 );
  u := 0;
  for i := 1 to k do
    u := (u * 10) + ord( s[i] ) - ord( '0' );

  logs := ln(u);
  logxy := 0;
  logs += ln(10) * (n - k);
  x := 1; y := 1;
  while (abs( logxy - logs) > 1e-6) do
    if (logs < logxy) then
      begin
        logxy -= ln( x );
        inc( x );
      end
    else
      begin
        inc( y );
        logxy += ln( y );
      end;
  writeln( x, ' ', y );
end.

Code mẫu của hieult

#include<cstdio>
#include<cmath>
#include<math.h>
#include<cstring>
#include<cstdlib>
#include<cassert>
#include<ctime>
#include<algorithm>
#include<iterator>
#include<iostream>
#include<cctype>
#include<string>
#include<vector>
#include<map>
#include<set>
#include<queue>
#include<list>
#define ep 1e-6
#define maxn 100011
#define oo 2000000001
#define modunlo 111539786
#define TR(c, it) for(typeof((c).begin()) it=(c).begin(); it!=(c).end(); it++)
//#define g 9.81
double const PI=4*atan(1.0);
//#include<conio.h>

using namespace std;

typedef pair<int, int> II;
typedef vector<int> VI;
typedef vector<II> VII;
typedef vector<VI> VVI;
typedef vector<VII> VVII;

double f[maxn];
string s;

int tim(double x){

    int u = 1, v = 100000, r;
    while(u < v){
        r = (u + v) / 2;
        if(f[r] > x - ep) v = r;
        else u = r + 1;    
    }
    if(abs(f[u] - x) < ep) return u;
    return 0;
}

int main(){

    //freopen("input.in","r",stdin);
    //freopen("output.out","w",stdout);

    cin >> s;
    double a = log(10) * (s.length() - 1);
    double res = 0, T = 1;
    for(int i = 0; i < s.length(); i++){
        res += T * (s[i] - '0');
        T /= 10;
    }
    a += log(res);

    f[0] = 0;
    for(int i = 1; i <= 100000; i++) f[i] = f[i - 1] + log(i);

    for(int i = 0; ; i++){

        res = a + f[i];
        if(tim(res)){
            printf("%d %d",i + 1, tim(res));
            return 0;
        }
    }
}

Code mẫu của skyvn97

#include<cstdio>
#include<cstring>
#include<map>
#define MAX   100100
#define m1   first
#define m2   second
using namespace std;
typedef long long ll;
typedef pair<ll,ll> pii;
const ll mod1=(ll)1e9+21;
const ll mod2=(ll)1e9+33;
map<pii,int> mp;
pii fac[MAX];
char p[MAX];
ll mp1,mp2;
int l;
void init(void) {
    scanf("%s",p);
    ll mul1=1;
    ll mul2=1;
    l=strlen(p);
    mp1=0;
    mp2=0;
    int i;
    for (i=l-1;i>=0;i=i-1) {
        mp1=(mp1+(p[i]-48)*mul1)%mod1;
        mp2=(mp2+(p[i]-48)*mul2)%mod2;
        mul1=(mul1*10)%mod1;
        mul2=(mul2*10)%mod2;
    }
    mp.clear();
}
void process(void) {
    int i,j;
    pii tmp;
    fac[0]=pii(1,1);
    for (i=1;i<=100000;i=i+1) {
        fac[i]=pii((fac[i-1].m1*i)%mod1,(fac[i-1].m2*i)%mod2);
        mp[fac[i]]=i;
    }
    for (i=0;i<100000;i=i+1) {
        tmp=pii((fac[i].m1*mp1)%mod1,(fac[i].m2*mp2)%mod2);
        j=mp[tmp];
        if (j>i) {
            printf("%d %d",i+1,j);
            return;
        }
    }
}
int main(void) {
    init();
    process();
    return 0;
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.