Editorial for Số thân thiệ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.

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

var i,a,b,re:longint;

function gcd(x,y:longint):longint;
begin
        if (x=0) or (y=0) then gcd:=x+y
        else
                if x>y then gcd:=gcd(y,x mod y)
                else gcd:=gcd(x,y mod x);
end;

function check(x:longint):boolean;
var s:string; i,l:longint;  c:char;  code:integer;
begin
        str(x,s);
        l:=length(s);
        for i:=1 to l shr 1 do
        begin
              c:=s[i]; s[i]:=s[l-i+1]; s[l-i+1]:=c;
        end;
        val(s,l,code);
        check:=gcd(x,l)=1;
end;

begin
        read(a,b);
        for i:=a to b do
                if check(i) then inc(re);
        writeln(re);
end.

Code mẫu của happyboy99x

#include <cstdio>

int rev( int n ) {
    int res = 0;
    while(n) {
        res = res * 10 + n % 10;
        n /= 10;
    }
    return res;
}

int gcd( int a, int b ) {
    while(b) {
        int t = b;
        b = a % b;
        a = t;
    }
    return a;
}

int main() {
    int a, b; scanf( "%d%d", &a, &b );
    int count = 0;
    for( int i = a; i <= b; ++i ) if( gcd(i, rev(i)) == 1 ) ++count;
    printf( "%d\n", count );
    return 0;
}

Code mẫu của ladpro98

program nknumfre;
uses    math,SysUtils;
var     a,b:longint;
        dao:array[1..300001] of longint;
        count,i:longint;
procedure init;
var     i,j:longint;
        s,s2:string;
begin
        for i:=a to b do
        begin
                s2:='';
                str(i,s);
                for j:=length(s) downto 1 do s2:=s2+s[j];
                dao[i]:=StrToInt(s2);
        end;

end;

function gcd(a,b:longint):longint;
begin
        if a mod b = 0 then exit(b)
        else exit(gcd(b, a mod b));
end;

begin
        count:=0;
        readln(a,b);
        init;
        for i:=a to b do
        begin
                if gcd(i,dao[i]) = 1 then inc(count);
        end;
        writeln(count);
end.

Code mẫu của RR

var
  i,a,b,cnt:longint;

function gcd(a,b:longint):longint;
    begin
      if (a=0) or (b=0) then exit(a+b)
      else exit(gcd(b,a mod b));
    end;

function check(i:longint):boolean;
    var
      u,v:longint;
    begin
      u:=0; v:=i;
      while (i>0) do
        begin
          u:=u*10+i mod 10;
          i:=i div 10;
        end;
      exit(gcd(u,v)=1);
    end;

begin
  read(a,b);
  cnt:=0;
  for i:=a to b do
    if check(i) then inc(cnt);
  writeln(cnt);
end.

Code mẫu của hieult

#include <stdio.h>
#include <math.h>
main()
{
int a,b,t,m,N,N1,A[5],k=0;
scanf("%d %d",&a,&b);
for(int n=a;n<=b;n++)
  {
  N=n;
  N1=n;
  t=0;
  m=0;
  for(int i=0;i<5;i++)
    {
    if(N==0)
      break;
    else
      t++;
    A[i]=N%10;
    N=N/10;
    }
  for(int i=0;i<t;i++)
    m=m+A[i]*pow(10,(t-i-1));
  while(1)
    {
    if(m%N1==0)
      {
      if(N1==1)
        k++;
      break;
      }
    else
      m=m%N1;
    if(N1%m==0)
      {
      if(m==1)
        k++;
      break;
      }
    else
      N1=N1%m;
    }
  }
printf("%d",k);
}

Code mẫu của ll931110

Program NKNUMFRE;
        Const
                input  = '';
                output = '';
        Var
                F: array[1..5] of longint;
              a,b: longint;
                q: longint;

Procedure init;
          Var
                fi: text;
          Begin
                Assign(fi, input);
                        Reset(fi);
                        Readln(fi, a, b);
                Close(fi);
          End;

Function eculide(x,y: longint): longint;
         Begin
                   Repeat
                                If x > y then x:= x - y
                           else if x < y then y:= y - x;
                   Until x = y;

                   eculide:= x;
         End;

Procedure rev(p: longint);
          Var
                i,k: longint;
          Begin
                F[1]:= p;

                For i:= 1 to 4 do
                        Begin
                                F[i + 1]:= F[i] div 10;
                                F[i]:= F[i] mod 10;
                        End;

                q:= 0;

                k:= 5;
                While F[k] = 0 do dec(k);

                For i:= 1 to k do q:= q * 10 + F[i];
          End;

Procedure numfre;
          Var
                num,i: longint;
                   fo: text;
          Begin
                Assign(fo, output);
                        Rewrite(fo);

                num:= 0;
                For i:= a to b do
                        Begin
                                rev(i);
                                If eculide(i,q) = 1 then inc(num);
                        End;

                        Writeln(fo, num);
                Close(fo);
          End;


Begin
        init;
        numfre;
End.

Code mẫu của skyvn97

#include<stdio.h>
#define MAX   30500
long a,b,i;
long inv[MAX+5];
long gcd(long a,long b)
{
    if (a*b==0) return (0);
    if (a==b) return (a);
    if (a>b) return gcd(b,a);
    if (b%a==0) return (a);
    return (gcd(b%a,a));
}
long inver(long n)
{
    if (inv[n]>0) return (inv[n]);
    if (n<10) return (n);
    long p=1;
    while (p<=n) p=p*10;
    p=p/10;
    int b=n%10;
    int a=n/10;
    inv[n]=b*p+inver(a);
    return (inv[n]);

}
void getinverse(void)
{
     long i,tmp;
     for (i=1;i<=MAX;i=i+1) tmp=inver(i);              
}
int main(void)
{    
    getinverse(); 
    scanf("%ld",&a);
    scanf("%ld",&b);
    long count=0;
    for (i=a;i<=b;i=i+1)        
        {
         if (gcd(i,inv[i])==1) count++;
        }
    printf("%ld",count);    
}

Comments

Please read the guidelines before commenting.


There are no comments at the moment.