题目33：找出具有一种奇怪约分性质的所有分数

欧拉计划

Digit cancelling fractions

The fraction 49/98 is a curious fraction, as an inexperienced mathematician in attempting to simplify it may incorrectly believe that 49/98 = 4/8, which is correct, is obtained by cancelling the 9s.

We shall consider fractions like, 30/50 = 3/5, to be trivial examples.

There are exactly four non-trivial examples of this type of fraction, less than one in value, and containing two digits in the numerator and denominator.

If the product of these four fractions is given in its lowest common terms, find the value of the denominator.

题目：

分数 49/98 是一个奇怪的分数：当一个菜鸟数学家试图对其进行简化时，他可能会错误地可以认为通过将分子和分母上的

9 同时去除得到 49/98 = 4/8。但他得到的结果却是正确的。

我们将 30/50 = 3/5 这样的分数作为普通个例。

一共有四个这样的非普通分数，其值小于 1，并且包括分子和分母都包括 2 位数。

如果将这四个分数的乘积约分到最简式，分母是多少？

迷雾少年

16/64
26/65
49/98
19/95

/输入2个数字去除相同的数字 返回相除结果
float calc2(int a,int b)
{
        float a1 = a%10;      //a的个位数
        float a2 = (a/10)%10; //a的十位数

        float b1 = b%10;      //b的个位数
        float b2 = (b/10)%10; //b的十位数
        if(a1==b1) return a2/b2;
        else if(a1==b2)
        {
                return a2/b1;
        }
        else if(a2==b1)return a1/b2;
        return 0;
}
int main() 
{ 
        
        for (float fenmu=1;fenmu<100;fenmu++)
        {
                for (float fenzi=1;fenzi<fenmu;fenzi++)
                {
                        if(calc2(fenzi,fenmu) == fenzi/fenmu )
                        {
                                cout<<fenzi<<"/"<<fenmu<<endl;
                        }
                }
        }
        return 0;
        
} 

愤怒的大头菇

list1 = []
count_i=1
count_j=1
for i in range(10,100):
      for j in range(10,100):
            if i < j:
                  str_1 = str(i)
                  if str_1[0]!=str_1[1] and str_1[1]!='0':
                        for each in str(i):
                              if each in str(j):
                                    temp = int(str(i).replace(each,'',1))
                                    tmp = int(str(j).replace(each,'',1))
                                    if (tmp!=0) and (temp/tmp == i/j) :
                                          count_i *=i
                                          count_j *=j
list2 = []
def gcd(x,y):
      if y:
            return gcd(y,x%y)
      else:
            return x
x = gcd(count_i,count_j)
print(int(count_j/x))

结果是100

芒果加黄桃

# encoding:utf-8
# pandigital 之和
from time import time 
def isUc(m, n):
    if len(str(m).strip(str(n))) == len(str(m)):
        return False
    m1 = str(m).strip(str(n))
    n1 = str(n).strip(str(m))
    if not m1 or not n1:
        return False
    if int(m1) / int(n1) == m / n:
        return True
    return False
def euler033():
    l_result = []
    for i in range(11, 100):
        if i % 10 == 0 or i % 11 == 0:
            continue
        for j in range(11, i):
            if j % 10 == 0 or j % 11 == 0:
                continue
            if isUc(j, i):
                print(i, j)
                l_result.append(i)
    print(sum(l_result))           
if __name__ == '__main__':
    start = time() 
    euler033()
    print('cost %.6f sec' % (time() - start))

64 16
65 26
95 19
98 49
322
cost 0.006003 sec

渡风

此代码使用matlab编程
Problem33所用时间为1.2507秒
Problem33的答案为100

% Problem33.m
% 最后编辑时间：17-06-05 0:18 
% 问题：求所有非正常约分的分数的乘积的分母
tic

Up = 1;
Down = 1;
for aa = 99 : -1 : 12
    Deno = aa;
    for bb = Deno - 1: -1: 11
        Elem = bb;
        NewDeno = num2str(Deno);
        OtherDeno = str2double(NewDeno(2));

        NewElem = num2str(Elem);
        OtherElem = str2double(NewElem(1));
        if OtherElem / OtherDeno == Elem / Deno ...
                && strcmp(NewDeno(1),NewDeno(2)) == 0 && strcmp(NewElem(1),NewElem(2)) == 0 && strcmp(NewDeno(1),NewElem(2)) == 1
            Up = Up * Elem;
            Down = Down *Deno;
        end
    end
end
Gcd = gcd(Up,Down);
Output = Down / Gcd;
toc 
disp('此代码使用matlab编程')
disp(['Problem33所用时间为',num2str(toc),'秒'])
disp(['Problem33的答案为',num2str(Output)])

迷雾少年 发表于 2016-8-29 17:03
16/64
26/65
49/98

去除普通个例

Trami

c = []
for i in range(10, 100):
    c.append(i)

d = []
for i in range(10, 100):
    d.append(i)

a = []
for item in c:
    # print(item)
    for item1 in str(item):
        a.append(item1)  # 最新的数据都是-1,-2

b = []
for item in d:
    # print(item)
    for item1 in str(item):
        b.append(item1)

for i in range(0, 180, 2):
    for j in range(0, 180, 2):
        A = int(a[i])
        B = int(a[i + 1])
        C = int(b[j])
        D = int(b[j+1])
        if D == 0 or C == 0:
            continue

        if (A*10 + B) != (C*10 + D):
            if A == D:
                if (A*10 + B) / ((C*10 + D)*1.0) == B/(C*1.0):
                    print((A*10 + B), (C*10 + D))
                    print('-------1-------')
            if A == C:
                if (A*10 + B) / ((C*10 + D)*1.0) == B/(D*1.0):
                    print((A*10 + B), (C*10 + D))
                    print('-------2-------')
            if B == C:
                if (A*10 + B) / ((C*10 + D)*1.0) == A/(D*1.0):
                    print((A*10 + B), (C*10 + D))
                    print('-------3-------')
            if B == D:
                if (A*10 + B)/((C*10 + D)*1.0) == A/(C*1.0):
                    print((A*10 + B), (C*10 + D))
                    print('-------4-------')

k往事如烟k

['16/64', '19/95', '26/65', '49/98']
322
cost 0.000000 sec

from time import time

def EP033():
    list1 = []
    for a in range(10, 100):
        for b in range(a + 1, 100):
            if (a // 10 == b // 10 or a // 10 == b % 10 or a % 10 == b // 10 or a % 10 == b % 10) and (
                    a % 10 != 0 and b % 10 != 0):
                list1.append(str(a // 10) + str(a % 10) + "/" + str(b // 10) + str(b % 10))

    list2 = []

    for each in list1:
        if each[0] == each[3]:
            list2.append(each[1:3] + each[4])
        elif each[0] == each[4]:
            list2.append(each[1:4])
        elif each[1] == each[3]:
            list2.append(each[0] + each[4])
        else:
            list2.append(each[0] + each[3])

    value_list1 = []
    value_list2 = []
    for each1 in list1:
        value_list1.append(round(int(each1[:2]) / int(each1[3:]), 3))

    for each2 in list2:
        value_list2.append(round(int(each2[0]) / int(each2[-1]), 3))

    list3 = []
    for i in range(len(list1)):
        if value_list1[i] == value_list2[i]:
            list3.append(list1[i])

    print(list3)
    sum = 0
    for each3 in list3:
        sum += int(each3[3:])
    print(sum)

if __name__ == '__main__':
    start = time()
    EP033()
    print('cost %.6f sec' % (time() - start)

王小召

分子分母：[(49, 98), (19, 95), (16, 64), (26, 65)]
化简分母：[100.0]
用时：0.156001秒

import functools
import time


def get_strange_list():
    result = []
    s_list = []
    # x > y
    for x in range(11, 100):
        for y in range(11, x):
            if not x % 10 and not y % 10:
                continue
            for each_letter in str(x):
                if each_letter in str(y) \
                        and x != y \
                        and int(str(y).replace(each_letter, '', 1)) != 0 \
                        and int(str(x).replace(each_letter, '', 1))/int(str(y).replace(each_letter, '', 1)) == x/y:
                    s_list.append((y, x))
    s_list = list(set(s_list))

    # 求 x,y (x<y) 的最大公约数
    x = functools.reduce(lambda x1, x2: x1*x2, [each[1] for each in s_list])
    y = functools.reduce(lambda x1, x2: x1 * x2, [each[0] for each in s_list])
    tmp = y
    while True:
        if not y % tmp and not x % tmp:
            result.append(x/tmp)
            break
        else:
            tmp -= 1
    return s_list, result
strange_list, result = get_strange_list()

print("分子分母：{}\n化简分母：{}\n用时：{}秒".format(strange_list, result, time.process_time()))

永恒的蓝色梦想

C++ 0ms

#include<iostream>
using namespace std;


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


bool judge(int a, int b) {
    int c = a / 10, d = b % 10, e, f;
    return a % 10 == b / 10 && a / (e = gcd(a, b)) == c / (f = gcd(c, d)) && b / e == d / f;
}


int main() {
    int nume = 1, deno = 1, i, j;

    for (i = 10; i < 100; i++) {
        for (j = i + 1; j < 100; j++) {
            if (judge(i, j)) {
                nume *= i;
                deno *= j;
            }
        }
    }

    cout << deno / gcd(nume, deno) << endl;
    return 0;
}

debuggerzh

100

Process returned 0 (0x0)   execution time : 0.029 s
Press any key to continue.
暴力枚举，同时推得一些性质

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

bool judge(int a,int b,int c,int d){
  return a * b == c * d;
}

int gcd(int x,int y){
  int r;
  while(y){
    r = x % y;
    x = y;
    y = r;
  }
  return x;
}

int main(){
  int numertr = 1,divisr = 1;//初始化分子分母

  for (int a1 = 1;a1 < 10;a1++){
    for (int a2 = a1+1;a2 < 10;a2++){
      int a = a1 * 10 + a2;
      int b;

      for (int a3 = a1+1;a3 < 10;a3++){
        b = a3 * 10 + a1;
        if (judge(a,a3,b,a2)) { numertr *= a2; divisr *= a3; }
      }

      for (int a4 = 1;a4 < 10;a4++){
        b = a2 * 10 + a4;
        if (judge(a,a4,b,a1)) { numertr *= a1; divisr *= a4; }
      }
    }
  }
  divisr /= gcd(numertr,divisr);
  cout << divisr << endl;
  return 0;
}

有马_冬巳

start = time.time()

for a in range(10,50):
    if a % 10 != 0:
        for b in range(10,100):
            if b % 10 != 0 and a != b :
                check = 0
                sa = list(str(a))
                sb = list(str(b))
                for each in sa:
                    if each in sb:
                        same = each
                        check += 1
                if check == 1:
                    sa.remove(same)
                    sb.remove(same)
                    if a / b == int(sa[0]) / int(sb[0]):
                            print("%d / %d" %(a,b))

end = time.time()
print("共用时%f秒" %(end - start))

16 / 64
19 / 95
26 / 65
49 / 98
共用时0.004488秒

有马_冬巳

start = time.time()

numer = 1
dino = 1
for a in range(10,50):
    if a % 10 != 0:
        for b in range(10,100):
            if b % 10 != 0 and a != b :
                check = 0
                sa = list(str(a))
                sb = list(str(b))
                for each in sa:
                    if each in sb:
                        same = each
                        check += 1
                if check == 1:
                    sa.remove(same)
                    sb.remove(same)
                    if a / b == int(sa[0]) / int(sb[0]):
                            numer *= a
                            dino *= b
                            print("%d / %d" %(a,b))

print("约分后分母为: %d" %(int(dino/numer)))


end = time.time()
print("共用时%f秒" %(end - start))

16 / 64
19 / 95
26 / 65
49 / 98
约分后分母为: 100
共用时0.003944秒

a1351468657

#include <stdio.h>

int MaxDiv(int, int);
int MaxDiv(int m, int n)
{
        if (m == 0 || n == 0)
        {
                printf("有数字为0\n");
                return -1;
        }
        int max, min, temp;
        max = m > n ? m : n;
        min = m < n ? m : n;
        while (max % min)
        {
                temp = max % min;
                max = min;
                min = temp;
        }
        return min;
}


main()
{
        int i, j, a, b, c, d, num = 1, den = 1;
        double x, y;

        for (i = 11; i < 100; i++)
        {
                for (j = i + 1; j < 100; j++)
                {
                        a = i % 10;
                        b = i / 10;
                        c = j % 10;
                        d = j / 10;
                        if (a == 0 || b == 0 || c == 0 || d == 0)
                        {
                                continue;
                        }

                        if (a == c)
                        {
                                x = (double)b / d;
                                y = (double)i / j;
                                if (x == y)
                                {
                                        num *= i;
                                        den *= j;
                                        printf("%d / %d\n", i, j);
                                }
                        }
                        if (a == d)
                        {
                                x = (double)b / c;
                                y = (double)i / j;
                                if (x == y)
                                {
                                        num *= i;
                                        den *= j;
                                        printf("%d / %d\n", i, j);
                                }
                        }
                        if (b == c)
                        {
                                x = (double)a / d;
                                y = (double)i / j;
                                if (x == y)
                                {
                                        num *= i;
                                        den *= j;
                                        printf("%d / %d\n", i, j);
                                }
                        }
                        if (b == d)
                        {
                                x = (double)a / c;
                                y = (double)i / j;
                                if (x == y)
                                {
                                        num *= i;
                                        den *= j;
                                        printf("%d / %d\n", i, j);
                                }
                        }
                }
        }
        i = MaxDiv(num, den);
        printf("%d\n", den / i);

}

答案为：
16 / 64
19 / 95
26 / 65
49 / 98

100

ft215378

#找出具有一种奇怪约分性质的所有分数
from time import *
def deal_string(x, y):
    if str(x)[0] == str(y)[0]:
        return int(str(x)[1]) / int(str(y)[1])
    elif str(x)[0] == str(y)[1]:
        return int(str(x)[1]) / int(str(y)[0])
    elif str(x)[1] == str(y)[0]:
        return int(str(x)[0]) / int(str(y)[1])
    elif str(x)[1] == str(y)[1]:
        return int(str(x)[0]) / int(str(y)[0])

def get_strange_num():
    strange_num = []
    for a in range(10, 100):
        for b in range(10, 100):
            if a % 10 != 0 and b % 10 != 0:
                if a < b and (a / b) == deal_string(a, b):
                    strange_num.append('%s/%s' % (a, b))
    return strange_num
start = time()
result = get_strange_num()

#计算
fenzi = 1
fenmu = 1
for each in result:
    fenzi *= int(each[0] + each[1])
    fenmu *= int(each[3] + each[4])
end = time()
print(fenmu//fenzi)
print("用时：%.9f秒" % (end - start))

guosl

/*
答案：100
耗时：0.0000015秒
*/
#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int x, int y)
{
  if (y == 0)
    return x;
  int z = x % y;
  while (z != 0)
  {
    x = y;
    y = z;
    z = x % y;
  }
  return y;
}

int main(void)
{
  int n = 1, d = 1;//分别保存特殊分数之积的分子和分母
  //这样的特殊分数只牵涉到三个数，我们分别枚举它们
  for (int a = 1; a <= 9; ++a)
  {
    for (int b = 0; b <= 9; ++b)
    {
      for (int c = 1; c <= 9; ++c)
      {
        int x = 10 * a + b;//构造分子
        int y = 10 * b + c;//构造分母
        if (x == 0 || y == 0)
          continue;
        if (x < y)//检查第一个要求
        {
          if (x * c == y * a)//检查第二个要求
          {
            //保存结果
            n *= a;
            d *= c;
          }
        }
        else
        {
          swap(x, y);//相同的数字位置调换一下
          if (x < y)//检查第一个要求
          {
            if (a * x == c * y)//检查第二个要求
            {
              //保存结果
              n *= c;
              d *= a;
            }
          }
        }
      }
    }
  }
  int p = gcd(n, d);
  d /= p;//约简分数
  cout << d << endl;//输出分母
  return 0;
}

TLM

这个应该会快一些，但是计算量实在是太小了。重复10000测时间
100
Time:0.17248201370239258s

"""
(10i+j)/(10j+k)=i/k  ==>  (9i+j)k=10ij
(10i+j)/(10k+i)=j/k  ==>  (9k+i)j=10ik

(9i+j)k=10ij ==> k=10ij/(9i+j)
"""
import time
st=time.time()
def get():
    # a=[]
    b=1
    c=1
    for i in range(1,10):
        for j in range(10):
            if j==i:
                continue
            if not 10*i*j%(9*i+j)==0:
                continue
            k=10*i*j//(9*i+j)
            if i==k or j==k:
                continue
            # a.append((min(i,k),j,max(i,k)))
            b,c=b*min(i,k),c*max(i,k)
    bb,cc=b,c
    while bb>0 and cc>0:
        if bb<cc:
            cc=cc%bb
        else:
            bb=bb%cc
    return c//max(bb,cc)
for i in range(10000):
    get()
print(get())
print('Time:{}s'.format(time.time()-st))

mathtimes

$ time ./main-v2
100

real        0m0.001s
user        0m0.000s
sys        0m0.001s

fn gcd(x:usize,y:usize) -> usize {
    let (mut b, mut l) = (x, y);
    if b < l {
        (b,l) = (l,b)
    }
    while l != 0 {
        b %= l;
        (b,l) = (l,b)
    }
    b
}
fn bits(x: usize) -> usize {
    let mut x = x;
    let mut ans = 0;
    while x != 0 && x % 10 != 0 {
        ans ^= 1 << (x % 10 - 1);
        x /= 10;
    }
    ans
}

fn main() {
    let mut v = vec![];
    for i in 10..99 {
        for j in (i + 1)..=99 {
            let t = bits(i)&bits(j);
            if t.count_ones() != 1 {continue;}
            let ri = (bits(i)^t).trailing_zeros() as usize + 1;
            let rj = (bits(j)^t).trailing_zeros() as usize + 1;
            if ri * j == rj * i {
                v.push((ri, rj));
            }
        }
    }
    let i = v.iter().map(|x| x.0).product::<usize>();
    let j = v.iter().map(|x| x.1).product::<usize>();
    println!("{}", j / gcd(i, j));
}