leetcode

leetcode1362.最接近的因数

class Solution{
    public int[] closestDivisors(int num){
        int divisor=num==1?num+1:num+2;
        int i=(int)Math.sqrt(divisor);
        while(divisor>1){
            i--;
        }
        return new int[](i,divisor/i);
    }
}

class Solution(object):
	def closestDivisor(self,num):
        divisor = num + 1 if num == 1 else num + 2
        i=int(math.sqrt(divisor))
        while divisor > 1:
    		i -= 1
        return [i,divisor/i]
#上一个好一点
class Solution:
    def closestDivisors(self, num):
        #------------------中心开花----------------
        def calc(num):
            for x in range(int(num ** 0.5), 0, -1):
                if num % x == 0:
                    return [x, num // x]
        res1 = calc(num + 1)
        res2 = calc(num + 2)
        return res1 if abs(res1[0]-res1[1]) < abs(res2[0]-res2[1]) else res2

package main

import (
    "fmt"
    "math"
)

func closestDivisors(num int) []int {
    divisor := num + 1
    if num == 1 {
        divisor = num + 1
    } else {
        divisor = num + 2
    }
    i := int(math.Sqrt(float64(divisor)))
    for divisor%i > 1 {
        i--
    }
    return []int{i, divisor / i}
}

二叉搜索树

二叉搜索树（Binary Search Tree，BST）是一种基于二叉树的数据结构。它具有以下性质：

1. 对于任意一个节点，它的左子树中的所有节点的值都小于该节点的值。
2. 对于任意一个节点，它的右子树中的所有节点的值都大于该节点的值。
3. 左右子树也分别为二叉搜索树。

因此，二叉搜索树中的节点按照从小到大的顺序排列。它支持插入、删除和查找操作，它们的时间复杂度都是 O(log n)。在一些特殊情况下，二叉搜索树的高度可能会退化为链表，这时候操作的时间复杂度会退化为 O(n)。

二叉搜索树可以用来实现一些高效的算法，如二叉搜索、二叉排序树、AVL树、红黑树等。它也被广泛应用于数据库、搜索引擎、文件系统等领域。

leetcode108

class Solution{
    public TreeNode sortedArrayToVST(int[] nums){
        return helper(nums,0,nums.length-1);
    }
    public TreeNode helper(int []nums,int left,int right){
        if (left>right){
            return null;
        }
        int mid=(left+right)/2;
        TreeNode root=new TreeNode(nums[mid]);
        root.left=helper(nums,left,mid-1);
        root.right=helper(nums.mid+1,right);
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def sortedArrayToBST(self,nums:List[int])->TreeNode:
        def helper(left,right):
            if left>right:
                return None
           	mid=(left+right)//2
            root=TreeNode(nums[mid])
            root.left=helper(left,mid-1)
            root.right=helper(mid+1,right)
            return root
        return helper(0,len(nums)-1)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func sortedArrayToBST(nums []int) *TreeNode {
    return helper(nums,0,len(nums)-1)
}
func helper(nums []int,left int,right int) *TreeNode{
    if left>right{
        return nil
    }
    mid:=(left+right)/2
    root:=&TreeNode{Val:nums[mid]}
    root.Left=helper(nums,left,mid-1)
    root.Right=helper(nums,mid+1,right)
    return root
}

leetcode1382

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    List<Integer> inorderSeq=new ArrayList<Integer>();
    public TreeNode balanceBST(TreeNode root) {
        getInorder(root);
        return build(0,inorderSeq.size()-1);
    }
    public void getInorder(TreeNode tree){
        if(tree.left!=null){
            getInorder(tree.left);
        }
        inorderSeq.add(tree.val);
        if(tree.right!=null){
            getInorder(tree.right);
        }
    }
    public TreeNode build(int l,int r){
        int mid=(l+r)>>1;
        TreeNode root=new TreeNode(inorderSeq.get(mid));
        if(l<=mid-1){
            root.left=build(l,mid-1);
        }
        if(mid+1<=r){
            root.right=build(mid+1,r);
        }
        return root;
    }
}

# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, val=0, left=None, right=None):
#         self.val = val
#         self.left = left
#         self.right = right
class Solution:
    def inOrder(self,root,nums):
        if root==None:
            return
        self.inOrder(root.left,nums)
        nums.append(root.val)
        self.inOrder(root.right,nums)
    def process(self,nums,left,right):
        if left>right:
            return None
        mid=(left+right)//2
        root=TreeNode(nums[mid])
        root.left=self.process(nums,left,mid-1)
        root.right=self.process(nums,mid+1,right)
        return root
    def balanceBST(self, root: TreeNode) -> TreeNode:
        nums=[]
        self.inOrder(root,nums)
        return self.process(nums,0,len(nums)-1)

/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func balanceBST(root *TreeNode) *TreeNode {
    nums:=[]int{}
    var inorder func(node *TreeNode)
    inorder =func(node *TreeNode){
        if node==nil{
            return
        }
        inorder(node.Left)
        nums=append(nums,node.Val)
        inorder(node.Right)
    }
    inorder(root)
    var buildTree func(l,r int) *TreeNode
    buildTree=func(l,r int) *TreeNode{
        mid:=(l+r)>>1
        node:=&TreeNode{Val:nums[mid]}
        if l<=mid-1{
            node.Left=buildTree(l,mid-1)
        }
        if r>=mid+1{
            node.Right=buildTree(mid+1,r)
        }
        return node
    }
    return buildTree(0,len(nums)-1)
}

#AVL旋转平衡二叉树
旋转的情况一共有4种情况：
新加入节点为 node.left 的左孩子， height(node.left) - height(node.right) > 1 。直接对node节点右旋。
新加入节点为 node.left 的右孩子， height(node.left) - height(node.right) > 1 。这时候要先对node.left左旋，调整为1的情况，再进行右旋。
新加入节点为 node.right 的右孩子， height(node.right) - height(node.left) > 1 。直接对node节点左旋。
新加入节点为 node.right 的左孩子， height(node.right) - height(node.left) > 1 。这时候要先对node.right右旋，调整为3的情况，再进行左旋。

class Solution{
    public TreeNode balanceBST(TreeNode root){
        if (root==null){
            return null;
        }
        Map<TreeNode,Integer> nodeHeight=new HashMap<>();
        TreeNode newRoot=null;
        Deque<TreeNode> stack=new LinkedList<>();
        TreeNode node=root;
        //先序遍历,利用栈很巧妙
        while(node!=null||!stack.isEmpty()){
            if(node!=null){
                newRoot=insert(newRoot,node.val,nodeHeight);
                stack.push(node);
                node=node.left;
            }
            else{
                node=stack.pop();
                node=node.right;
            }
        }
        return newRoot;
    }
    private TreeNode insert(TreeNode root,int val,Map<TreeNode,Integer> nodeHeight){
        if(root==null){
            root=new TreeNode(val);
            nodeHeight.put(root,1);
            return root;
        }
        TreeNode node=root;
        int cmp=val-node.val;
        if(cmp<0){
            //左子树插入
            node.left=insert(root.left,val,nodeHeight);
            if(nodeHeight.getOrDefault(node.left,0)-nodeHeight.getOrDefault(node.right,0)>1){
                if(val>node.left.val){
                    node.left=rotateLeft(node.left,nodeHeight);
                }
                node=rotateLeft(node,nodeHeight);
            }
        }
        else if(cmp>0){
            node.right=insert(root.right,val,nodeHeight);
        }
        if(nodeHeight.getOrDefault(node.right,0)-nodeHeight.getOrDefault(node.left,0)>1){
            if(val<node.right.val){
                node.right=rotateRight(node.right,NodeHeight);
            }
            node=rotateLeft(node,nodeHeight);
        }
    }else{
        return node;
    }
    int height=getCurNodeNewHeight(node,nodeHeight);
    nodeHeight.put(node,height);
    return node;
}


private TreeNode rotateLeft(TreeNode node,Map<TreeNode,Integer> nodeHeight){
    TreeNode right=node.right;
    node.right=right.left;
    right.left=node;
    int newNodeHeight=getCurNodeNewHeight(node,nodeHeight);
    nodeHeight.put(node,newNodeHeight);
    int newRightHeight=Math.max(newNodeHeight,nodeHeight.getOrDefault(right.right,0))+1;
    nodeHeight.put(right,newRightHeight);
    return right;
}

private TreeNode rotateRight(TreeNode node,Map<TreeNode,Integer> nodeHeight){
        // ---指针调整
        TreeNode left = node.left;
        node.left = left.right;
        left.right = node;
        // ---高度更新
        // 先更新node节点的高度，这个时候node是right节点的左孩子
        int newNodeHeight = getCurNodeNewHeight(node,nodeHeight);
        // 更新node节点高度
        nodeHeight.put(node,newNodeHeight);
        // newNodeHeight是现在left节点右子树高度，原理一样，取现在right左右子树最大高度+1
        int newLeftHeight = Math.max(newNodeHeight,nodeHeight.getOrDefault(left.left,0)) + 1;
        // 更新原left节点高度
        nodeHeight.put(left,newLeftHeight);
        return left;
    }

    /**
     * 获取当前节点的新高度
     * @param node node
     * @param nodeHeight node高度缓存
     * @return 当前node的新高度
     */
    private int getCurNodeNewHeight(TreeNode node,Map<TreeNode,Integer> nodeHeight){
        // node节点的高度，为现在node左右子树最大高度+1
        return Math.max(nodeHeight.getOrDefault(node.left,0),nodeHeight.getOrDefault(node.right,0)) + 1;
    }
}

左旋转

右旋转

双旋转

码蹄集：永恒之2

分析如下：

import java.util.Scanner;

class mati2181 {

    public static void main(String[] args) {
        long n,ans = 0;
        final long mod=99999989;
        Scanner input = new Scanner(System.in);
        // code here
        n=input.nextInt();
        String s=input.next();
        input.close();
        long[] p=new long[15];
        long[] a=new long[15];
        p[0]=1;
        for(int i=1;i<=n;i++) {
            p[i] = p[i - 1] * 16;
        }
        for (int i=0;i<n;i++) {
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                a[i] = s.charAt(i) - '0';
            } else {
                a[i] = s.charAt(i) - 'A' + 10;
            }
        }
        for(int i=0;i<n;i++){
            long pre=0;long suf=0;
            for(int j=0;j<=i-1;j++){
                pre=pre*16+a[j];
            }
            for(int j=i+1;j<n;j++){
                suf=suf*16+a[j];
            }
            if(a[i]>2){
                ans=(ans+(pre+1)*p[(int)(n-i-1)]%mod)%mod;
            }
            else if(a[i]<2){
                ans=(ans+pre*p[(int)(n-i-1)]%mod)%mod;
            }
            else {
                ans=(ans+suf+1+pre*p[(int)(n-i-1)]%mod)%mod;
            }
        }
        System.out.println(ans);
    }
}

n = int(input())
s = input()

p = [1] * 15
a = [0] * 15
ans = 0
mod = 99999989

for i in range(1, n+1):
    p[i] = p[i - 1] * 16

for i in range(n):
    if s[i].isdigit():
        a[i] = int(s[i])
    else:
        a[i] = ord(s[i]) - ord('A') + 10

for i in range(n):
    pre, suf = 0, 0
    for j in range(i):
        pre = pre * 16 + a[j]
    for j in range(i + 1, n):
        suf = suf * 16 + a[j]
    if a[i] > 2:
        ans = (ans + (pre + 1) * p[n - i - 1]) % mod
    elif a[i] < 2:
        ans = (ans + pre * p[n - i - 1]) % mod
    else:
        ans = (ans + suf + 1 + pre * p[n - i - 1]) % mod

print(ans)

package main

import (
	"fmt"
)

func main() {
	var n int
	fmt.Scan(&n)

	var s string
	fmt.Scan(&s)

	p := make([]int, 15)
	a := make([]int, 15)
	ans := 0
	mod := 99999989

	p[0] = 1
	for i := 1; i <= n; i++ {
		p[i] = p[i-1] * 16
	}

	for i := 0; i < n; i++ {
		if s[i] >= '0' && s[i] <= '9' {
			a[i] = int(s[i] - '0')
		} else {
			a[i] = int(s[i] - 'A' + 10)
		}
	}

	for i := 0; i < n; i++ {
		pre, suf := 0, 0
		for j := 0; j <= i-1; j++ {
			pre = pre*16 + a[j]
		}
		for j := i + 1; j < n; j++ {
			suf = suf*16 + a[j]
		}
		if a[i] > 2 {
			ans = (ans + (pre+1)*p[n-i-1]) % mod
		} else if a[i] < 2 {
			ans = (ans + pre*p[n-i-1]) % mod
		} else {
			ans = (ans + suf + 1 + pre*p[n-i-1]) % mod
		}
	}

	fmt.Println(ans)
}

码蹄集：人脑计算机

import java.util.Scanner;
import java.util.*;

class Main {

    public static void main(String[] args) {

        Scanner input = new Scanner(System.in);
        // code here
        int n=input.nextInt();
        int[] a=new int[n-1];
        String[] b=new String[n-1];
        for(int i=0;i<n-1;i++){
            b[i]="";
        }

        for (int i=0;i<n-1;i++){
            a[i]=input.nextInt();
        }
        for (int i=0;i<n-1;i++){
            while (a[i]>0){
                b[i]=(a[i]%2)+b[i];
                a[i]=a[i]/2;
            }
        }
        for (int i=0;i<n-1;i++){
            System.out.println(b[i]);
        }
        input.close();
    }
}

import java.util.Scanner;
import java.util.Stack;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int t = scanner.nextInt();
        t--;
        while (t-- > 0) {
            int n = scanner.nextInt();
            Stack<Integer> st = new Stack<>();
            while (n > 0) {
                st.push(n % 2);
                n = n / 2;
            }
            while (!st.isEmpty()) {
                System.out.print(st.pop());
            }
            System.out.println();
        }
    }
}

#include<bits/stdc++.h>
using namespace std;
int t, n;
stack<int> st;
int main() {
	cin >> t;
	t--;
	while (t--)
	{
		cin >> n;
		while (n)
		{
			st.push(n % 2);
			n = n / 2;
		}
		while (!st.empty())
		{
			cout << st.top();
			st.pop();
		}
		cout << endl;
	}
	return 0;
}

t = int(input())
t -= 1

while t > 0:
    n = int(input())
    st = []
    while n > 0:
        st.append(n % 2)
        n = n // 2
    while st:
        print(st.pop(), end="")
    print()
    t -= 1

package main

import (
	"fmt"
)

func main() {
	var t int
	fmt.Scan(&t)
	t--

	for t > 0 {
		var n int
		fmt.Scan(&n)
		st := []int{}
		for n > 0 {
			st = append(st, n%2)
			n = n / 2
		}
		for len(st) > 0 {
			fmt.Print(st[len(st)-1])
			st = st[:len(st)-1]
		}
		fmt.Println()
		t--
	}
}

码蹄集：字符串构造

#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 7;
int n, k, pi[N];
char s[N];
void prefix_function(char* s, int len) {
	for (int i = 1; i < len; i++) {
		int j = pi[i - 1];
		while (j>0&&s[i]!=s[j])
		{
			j = pi[j - 1];
		}
		if (s[i] == s[j]) {
			j++;
		}
		pi[i] = j;
	}
}
int main() {
	cin >> n >> k >> s;
	prefix_function(s, n);
	for (int i = 1; i <= k; i++) {
		for (int j = 0; j < n - pi[n - 1]; j++) {
			cout << s[j];
		}
	}
	for (int i = n - pi[n - 1]; i < n; i++) {
		cout << s[i];
	}
	return 0;
}

需要学习KMP算法

码蹄集2077：密码

def main():
	#code here
	s=input()
	next=build_next(s)
	max=find_max_repeated(next)
	if max==0:
		print("Just a legend")
		return
	for i in range(len(next)):
		if(next[i]==max):
			max_index=i
			break
	str = ""
	for i in range(max_index-max+1,max_index+1):
		str+=s[i]
	print(str)


def build_next(patt):
	next = [0]
	prefix_len = 0
	i =1
	while(i<len(patt)):
		if(patt[prefix_len]==patt[i]):
			prefix_len+=1
			next.append(prefix_len)
			i+=1
		else:
			if prefix_len==0:
				next.append(0)
				i+=1
			else:
				prefix_len=next[prefix_len-1]
	return next
def find_max_repeated(arr):
	counts = [0] * 1000
	max_num = 0

	for num in arr:

		counts[num] += 1
	for i in range(len(counts)):
		if(counts[i])>1 and i>max_num:
			max_num=i
	return max_num




if __name__ == '__main__':
	main()

码蹄集：单条件和

#include<bits/stdc++.h> 

using namespace std;
int n;
unsigned int ans,a;
int main( )
{   
    cin>>n;
    scanf("%u",&ans);
    for(int i=2;i<=n;i++){
        scanf("%u",&a);
        ans=~ans|a;
    }
    cout<<ans;
    return 0;
}
C++




n = int(input())
ans = int(input()) & 0xffffffff  # 将 ans 转换为无符号数
for i in range(2, n + 1):
    a = int(input()) & 0xffffffff  # 将 a 转换为无符号数
    ans = ~ans | a
print(ans)
python




package main

import "fmt"

func main() {
    var n int
    fmt.Scan(&n)
    var ans uint32
    fmt.Scan(&ans)
    var a uint32
    for i := 2; i <= n; i++ {
        fmt.Scan(&a)
        ans = ^ans | a
    }
    fmt.Println(ans)
}

码蹄集：查找未出现的二进制

str=input().split()
str2=[]
for i in range(pow(2,len(str[0]))):
	str2.append(format(i,"0%db"%len(str)))
print(str2)
result=[x for x in str2 if x not in str]
print(result[0])

码蹄集：对称三进制

'''
@File    :   ternary.py    
@Contact :   zhangzhilong2022@gmail.com
@Modify Time      @Author    @Version    @Desciption
------------      -------    --------    -----------
2023/8/25 11:28   huahai2022      1.0         None
'''
def ternary2d(str):
	str_len=len(str)
	count=0
	for i in range(str_len):
		if str[i]=="-":
			count+=-1*3**(str_len-1-i)
		if str[i]=="0":
			pass
		if str[i]=="1":
			count+=1*3**(str_len-1-i)
	return count
n = int(input())
for i in range(n):
	s=input()
	print(ternary2d(s))

码蹄集：三进制转化为十进制

'''
@File    :   d2ternary.py    
@Contact :   zhangzhilong2022@gmail.com
@Modify Time      @Author    @Version    @Desciption
------------      -------    --------    -----------
2023/8/25 11:45   huahai2022      1.0         None
'''
def d2ternary(str):
	ternary=""
	num=int(str)
	if num==0:
		return 0
	if num>0:
		while num>0:
			remainder=num%3
			if remainder==0:
				ternary='0'+ternary
				num=num//3
			elif remainder==1:
				ternary='1'+ternary
				num=num//3
			else:
				ternary='-'+ternary
				num=num//3+1
	if num<0:
		num=abs(num)
		while num>0:
			remainder=num%3
			if remainder==0:
				ternary='0'+ternary
				num=num//3
			elif remainder==1:
				ternary='1'+ternary
				num=num//3
			else:
				ternary='-'+ternary
				num=num//3+1
		ternary_list = list(ternary)
		for i in range(len(ternary)):
			if ternary[i]=='1':
				ternary_list[i]="-"
			elif ternary[i]=="-":
				ternary_list[i]="1"
		ternary="".join(ternary_list)
	return ternary
n=int(input())
for i in range(n):
	s=input()
	print(d2ternary(s))

码蹄集：进制的综合

'''
@File    :   excel.py
@Contact :   zhangzhilong2022@gmail.com
@Modify Time      @Author    @Version    @Desciption
------------      -------    --------    -----------
2023/8/25 12:17   huahai2022      1.0         None
'''
import re
def num2letter(num):
	letter=""
	while num>0:
		a=num%26
		if a==0:
			letter='Z'+letter
			num=num//26-1
		else:
			letter=chr(a+64)+letter
			num=num//26
	return letter
def letter2num(letter):
	length=len(letter)
	num=0
	for i in range(length):
		num+=(ord(letter[i])-64)*26**(length-i-1)
	return num
def A2B(s):
	pattern="\\d+"
	matchs=re.findall(pattern,s)
	num2=int(matchs[1])
	return num2letter(num2)+matchs[0]

	#R 12 C 3转化为C12

def B2A(s):
	pattern=r"([A-Z]+)(\d+)"
	match=re.match(pattern,s)
	letter=match.group(1)
	num=match.group(2)
	letters="R"+num+"C"+str(letter2num(letter))
	return letters
n= int(input())
str_list=[]
for i in range(n):
	s=input()
	str_list.append(s)
	
for i in range(n):
	if re.match("R[0-9]*C[0-9]*",str_list[i]) is not None:
		print(A2B(str_list[i]))
	else:
		print(B2A(str_list[i]))



b

码蹄集：Good Num的数量

#思路：快速求幂的方法
def fast_power(base, exponent):
    result = 1
    while exponent > 0:
        if exponent % 2 == 1:
            result *= base%(10**9+7)
        base *= base%(10**9+7)
        exponent //= 2
    return result
def main():
    #code here
    k=int(input())
    mid1=k//2       #表示奇数
    if k%2==0:
        mid2=mid1
    else:
        mid2=mid1+1 #表示偶数
    print(fast_power(4,mid1)*fast_power(5,mid2)%(10**9+7))



if __name__ == '__main__':
    main();

码蹄集：幂和

#和上面一题的思路一致
def fast_power(base,exp):
    res=1
    while exp>0:
        if exp%2==1:
            res*=base%(998244353)
        base*=base%(998244353)
        exp=exp//2
    return res%998244353
def main():
    #code here
    n=int(input())
    count=0
    for i in range(1,n+1):
        count+=fast_power(i,i)%(998244353)
    print(count%998244353)


if __name__ == '__main__':
    main();

码蹄集：个数统计

def main():
    line=input()
    n=int(line.split(" ")[0])
    a=line.split(" ")[1]
    count=1
    count2=0
    for i in range(1,n+1):
        count=count*i
    for i in str(count):
        if i==a:
            count2+=1
    print(count2)


if __name__ == '__main__':
    main();

码蹄集：个数统计2

#编写代码要规范
def main():
    #code here
    line=input()
    n=int(line.split(" ")[0])
    b=line.split(" ")[1]
    len_b=len(b)
    count=1
    for i in range(1,n+1):
        count*=i
    count2=0
    count_str=str(count)
    for i in range(len(count_str)-len_b+1):
        if count_str[i:i+len_b]==b:
            count2+=1
    print(count2)


if __name__ == '__main__':
    main();

码蹄集：快速幂

def main():
    #code here
    line=input()
    a,b,c=line.split(" ")
    a=int(a)
    b=int(b)
    c=int(c)
    count=1
    while b>0:
        if b%2==1:
            count*=a%c
        a=a*a%c
        b=b//2
    print(count%c)

if __name__ == '__main__':
    main();

码蹄集：全部相同

def getMax(my_set:list):
    if len(my_set)==1:
        return my_set[0]
    for i in range(len(my_set)-1):
        if my_set[i]%my_set[-1]!=0:
            return 1
    return my_set[-1]
def main():
    #code here
    n=int(input())
    for i in range(n):
        m=int(input())
        list_m=[int(x) for x in input().split(" ")]
        my_set=set(list_m)
        my_set=sorted(my_set,reverse=True)
        if (len(my_set))==1:
            print("-1")
            return
        last_ele=my_set.pop()
        new_set=[x-last_ele for x in my_set]
        print(getMax(new_set))
        

if __name__ == '__main__':
    main();

码蹄集：石头剪刀布

#注意这个题目，不能直接将字符串扩展到n,会超时和超内存，另外注意整数和浮点数之间的
import math
def getMax(m1:int,m2:int):
    return int(m1*m2/math.gcd(m1,m2))
def main():
    n = int(input())
    m1 = input()
    m2 = input()
    m1_len=len(m1)
    m2_len=len(m2)
    toge=getMax(m1_len,m2_len)
    m1=m1*int(toge/m1_len)
    m2=m2*int(toge/m2_len)
    count1=0
    count2=0
    for i in range(toge):
        if m1[i]!=m2[i]:
            if (m1[i]=='R' and m2[i]=="P") or (m1[i]=="P" and m2[i]=="S") or (m1[i]=="S" and m2[i]=="R"):
                count1+=1
            else:
                count2+=1
    bei=int(n/toge)
    yu=int(n%toge)
    count3=0
    count4=0
    for i in range(yu):
        if m1[i]!=m2[i]:
            if (m1[i]=='R' and m2[i]=="P") or (m1[i]=="P" and m2[i]=="S") or (m1[i]=="S" and m2[i]=="R"):
                count3+=1
            else:
                count4+=1
    print(" ".join([str(count1*bei+count3),str(count2*bei+count4)]))



if __name__ == '__main__':
    main()

码蹄集：欧拉函数

from math import sqrt
def main():
    #code here
    n=int(input())
    ans=n
    for i in range(2,int(sqrt(n))+1):
        if n%i==0:
            ans=ans//i*(i-1)
        while n%i==0:
            n//=i
    if n>1:
        ans=ans//n*(n-1)
    print(ans)
    pass


if __name__ == '__main__':
    main();