Editorial for CALCULATE POW(2004,X) MOD 29


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 ar:array[2..4] of integer=(2,3,167);
var n,re,t,i,j,s:longint;
    m:array[2..4] of longint;
    a:array[2..4,1..100] of longint;
procedure init;
var i,j:byte;
begin
     a[2,1]:=2; a[3,1]:=3; a[4,1]:=22;
     for i:=2 to 4 do
     begin
          m[i]:=2;
          a[i,2]:=(a[i,1]*ar[i]) mod 29;
     end;
     for i:=2 to 4 do
     begin
          while a[i,m[i]]<>a[i,1] do
          begin
               inc(m[i]);
               a[i,m[i]]:=(a[i,m[i]-1]*ar[i]) mod 29;
          end;
          dec(m[i]);
     end;
end;

begin
     init;
     repeat
           read(n);
           if n=0 then break;
           t:=(2*n+1) mod m[2];
           if t=0 then t:=m[2];
           re:=(a[2,t]+28) mod 29;
           for i:=3 to 4 do
           begin
                t:=(n+1) mod m[i];
                if t=0 then t:=m[i];
                dec(t);
                s:=1;
                for j:=1 to t do s:=(s+a[i,j]) mod 29;
                re:=(re*s) mod 29;
           end;
           writeln(re);
     until false;
end.

Code mẫu của happyboy99x

#include<cstdio>

#define MOD 29

int powmod(int a, int n) {
    if(n == 0) return 1;
    int res = powmod(a, n/2);
    return n % 2 ? res * res * a % MOD : res * res % MOD;
}

int main() {
    int x;
    while(scanf("%d",&x) != EOF && x != 0) {
        printf("%d\n", (powmod(2,x+x+1)-1)*(powmod(3,x+1)-1)*powmod(2,MOD-2)*(powmod(167,x+1)-1)*powmod(166,MOD-2) % MOD);
    }
    return 0;
}

Code mẫu của ladpro98

#include <cstring>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <stack>
#include <bitset>
#include <algorithm>
#include <utility>
#include <sstream>
#include <fstream>
#include <iostream>
#include <iomanip>
#include <cstdio>
#include <cmath>
#include <climits>
#include <cstdlib>
#include <ctime>
#include <cassert>

#define FOR(i, a, b) for(int i = (a); i < (b); ++i)
#define REP(i, a, b) for(int i = (a); i <=(b); ++i)
#define REPD(i, a, b) for(int i = (a); i >=(b); --i)
#define TR(it, a) for(__typeof(a.begin()) it = a.begin(); it != a.end(); ++it)
#define RESET(a, v) memset(a, (v), sizeof(a))
#define SZ(a) (int(a.size()))
#define ALL(a) a.begin(), a.end()
#define PB push_back
#define MP make_pair
#define LL long long
#define LD long double
#define II pair<int, int>
#define X first
#define Y second
#define VI vector<int>
#define VII vector<II>
#define endl '\n'

using namespace std;

int powMod(int a, int p) {
  if (p == 1) return a % 29;
  int x = powMod(a, p >> 1);
  x = x * x % 29;
  if (p & 1) return x * a % 29;
  return x;
}

int cnt[2004];

int main() {
  ios::sync_with_stdio(0); cin.tie(0);
  #ifdef _LAD_
    freopen("MMOD29.in", "r", stdin);
  #endif // _LAD_
  int power;
  while (cin >> power) {
    if (power == 0) break;
    int x = 2004;
    RESET(cnt, 0);
    for (int i = 2; i <= x; ++i)
    while (x % i == 0) {
      cnt[i] += power;
      x /= i;
    }
    int ans = 1;
    FOR(i, 2, 2004)
    if (cnt[i]) {
      ans = ans * (powMod(i, cnt[i] + 1) + 28) * powMod(i - 1, 27) % 29;
    }
    cout << ans << endl;
  }
  return 0;
}

Code mẫu của RR

{$R+,Q+}
{$inline on}
uses math;
var
  x             :       longint;

function get(a,n:longint):longint;
    var
      k,p,t:longint;
    begin
      if n=0 then exit(0);
      if n=1 then exit(1);
      k:=n>>1;
      p:=get(a,k);
      t:=(p*p*(a-1)+p<<1) mod 29;
      if n and 1=0 then exit(t);
      exit(((a*t)+1) mod 29);
    end;

begin
  read(x);
  while (x>0) do
    begin
      writeln((get(2,2*x+1)*get(3,x+1)*get(167,x+1)) mod 29);
      read(x);
    end;
end.

Code mẫu của hieult

#include <stdio.h>
//#include <conio.h>
#include <math.h>
long f(long a,long n)
{
if(n==1)
  return a;
else if(n%2!=0)
  return a*f(a,n-1)%29;
else
  {
  double y=pow(f(a,n/2),2);
  long x=long(y);
  if(y-x>0.1) 
  return (x+1)%29;
  else return x%29;
  }
}
main()
{
long x[30],n,a,b,c,KQ;
for(long i=0;i<=28;i++)
  x[i]=(21*i)%29;      
while(scanf("%ld",&n)&&n>0)
  {
  a=f(2,2*n+1)-1;
  for(long i=0;i<=28;i++)
    if(f(22,n+1)-1==x[i])
      b=i;
  if(f(3,n+1)%2!=0)
    c=(f(3,n+1)-1)/2;
  else c=(f(3,n+1)+28)/2;
  //printf("%ld %ld %ld %ld ",a,b,c,f(22,n+1));
  KQ=a*b*c%29;
  printf("%ld\n",KQ);
  }
//getch();
}

Code mẫu của ll931110

#include <cstdio>
#include <iostream>
#define VAL 29
using namespace std;

int calc(int x, int p)
{
    int i,t;

    x = x % VAL;
    p = p % (VAL - 1);

    if (p == 0) return 0;
    else
    {    
         t = 1;
         for (i = 0; i < p; i++)
           t = (t * x) % VAL;

         t--;
         while (t % (x - 1) != 0)
             {
                  t += VAL;
             }      

         i = t / (x - 1);
         return i;
    }
}

int main()
{
    int v,n;

    do
    {
        cin >> n;
        if (n != 0)
        {
                 v = calc(2, 2 * n + 1);
                 v = (v * calc(3, n + 1)) % VAL;
                 v = (v * calc(167, n + 1)) % VAL;
                 cout << v << endl;
        }         
    }
    while (n != 0);
    return 0;
}

Code mẫu của khuc_tuan

// {$APPTYPE CONSOLE}
 {$mode delphi}

function pow(x,n : integer) : integer;
var
    t : integer;
begin
    if n=0 then pow := 1
    else
    begin
        t := pow(x,n div 2);
        if n mod 2 = 0 then pow := t * t mod 29
        else pow := t * t * x mod 29;
    end;
end;

var
    r, x : integer;

begin
    while true do
    begin
        read(x);
        if x=0 then break;
        r := 1;
        r := r * (28 + pow(3,x+1)) * pow(2, 27) mod 29;
        r := r * (28 + pow(167,x+1)) * pow( 166, 27) mod 29;
        r := r * (28 + pow(2,2*x+1)) mod 29;
        writeln(r);        
    end;
end.

Comments

Please read the guidelines before commenting.


There are no comments at the moment.