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

/输入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))

# 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))

% 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)])

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-------')

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)

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()))

#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;
}

#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))

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))

#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);

}

/*
答案：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;
}

"""
(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))

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));
}