算法计算器使用文档
说明：本项目对普通计算器进行了改进部分为：
初始：
- 普通计算器为只可对两个整数进行加减乘除
改进部分：
- 普通计算器采用栈实现，并可对浮点数进行一系列操作
- 算法计算器采用均为最优算法，对时间复杂度进行优化，如求幂（正常为for循环逐一相乘，此处采用快速幂算法）等
缺点部分：
- 本计算器设计时间有限，故所有整形运算均为int类型
- guass函数还未完成，其余均可使用
页面展示
首页： 分为两个入口，一个是常规的普通版计算器，一个是结合算法实现的算法版计算器
普通计算器
使用方法同普通计算器，均可实现整数以及小数计算，同时，在普通计算器的基础上添加了栈的实现，可以进行复合运算。
算法计算器
使用方式比较复杂，最后是其使用文档，可以对不同的运算进行快速处理，特别的是，后端的逻辑实现采用的均为算法较优的实现。
实现过程
1、创建一个新文件——Empty Views Activity
2、下面的感叹号是因为我已经创建过一个了（可以忽略）
3、等待Building
4、规划 代码实现部分：
理论上把我写的代码复制到对应位置上面即可运行
MainActivity实现登陆页面，然后对按钮进行跳转实现
MainActivity2实现普通计算器
MainActivity3实现算法计算器
步骤：
- 创建MainActivity，然后对activity_main.xml布局
- 写MainActivity代码逻辑
- 创建MainActivity2，然后对activity_main2.xml布局
- 写MainActivity2代码逻辑
- 创建类MathUtils，完成数学函数编写
- 创建MainActivity3，然后对activity_main3.xml布局
- 写MainActivity3代码逻辑
MainActivity——CODE：
package com.example.algoritmcalculator;
import android.content.Intent;
import android.os.Bundle;
import android.widget.Button;
import androidx.activity.EdgeToEdge;
import androidx.appcompat.app.AppCompatActivity;
import androidx.core.graphics.Insets;
import androidx.core.view.ViewCompat;
import androidx.core.view.WindowInsetsCompat;
public class MainActivity extends AppCompatActivity {
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
EdgeToEdge.enable(this);
setContentView(R.layout.activity_main);
ViewCompat.setOnApplyWindowInsetsListener(findViewById(R.id.main), (v, insets) -> {
Insets systemBars = insets.getInsets(WindowInsetsCompat.Type.systemBars());
v.setPadding(systemBars.left, systemBars.top, systemBars.right, systemBars.bottom);
return insets;
});
Button button = findViewById(R.id.button);
button.setOnClickListener(view -> {
Intent intent = new Intent(this, MainActivity2.class);
startActivity(intent);
});
Button button2 = findViewById(R.id.button2);
button2.setOnClickListener(view -> {
Intent intent = new Intent(this, MainActivity3.class);
startActivity(intent);
});
}
}
MainActivity2——CODE：
package com.example.algoritmcalculator;
import android.annotation.SuppressLint;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.TextView;
import android.widget.Toast;
import androidx.activity.EdgeToEdge;
import androidx.appcompat.app.AppCompatActivity;
import androidx.core.graphics.Insets;
import androidx.core.view.ViewCompat;
import androidx.core.view.WindowInsetsCompat;
import java.util.Stack;
public class MainActivity2 extends AppCompatActivity implements View.OnClickListener {
private final static String TAG = "CalculatorActivity";
private TextView tv_result; // 声明一个文本视图对象
private String operator = ""; // 运算符
private String firstNum = ""; // 第一个操作数
private String secondNum = ""; // 第二个操作数
private String result = ""; // 当前的计算结果
private String showText = ""; // 显示的文本内容
private Stack<Double> num = new Stack<>();
private Stack<Character> op = new Stack<>();
private int[] priority = new int[256];
{
priority['+'] = priority['-'] = 1;
priority['*'] = priority['/'] = 2;
}
@SuppressLint("MissingInflatedId")
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
EdgeToEdge.enable(this);
setContentView(R.layout.activity_main2);
ViewCompat.setOnApplyWindowInsetsListener(findViewById(R.id.main2), (v, insets) -> {
Insets systemBars = insets.getInsets(WindowInsetsCompat.Type.systemBars());
v.setPadding(systemBars.left, systemBars.top, systemBars.right, systemBars.bottom);
return insets;
});
// 从布局文件中获取名叫tv_result的文本视图
tv_result = findViewById(R.id.tv_result);
// 下面给每个按钮控件都注册了点击监听器
findViewById(R.id.btn_cancel).setOnClickListener(this); // “取消”
findViewById(R.id.btn_divide).setOnClickListener(this); // “除法”
findViewById(R.id.btn_multiply).setOnClickListener(this); // “乘法”
findViewById(R.id.btn_clear).setOnClickListener(this); // “清除”
findViewById(R.id.btn_seven).setOnClickListener(this); // 7
findViewById(R.id.btn_eight).setOnClickListener(this); // 8
findViewById(R.id.btn_nine).setOnClickListener(this); // 9
findViewById(R.id.btn_plus).setOnClickListener(this); // “加法”
findViewById(R.id.btn_four).setOnClickListener(this); // 数字4
findViewById(R.id.btn_five).setOnClickListener(this); // 数字5
findViewById(R.id.btn_six).setOnClickListener(this); // 数字6
findViewById(R.id.btn_minus).setOnClickListener(this); // “减法”
findViewById(R.id.btn_one).setOnClickListener(this); // 数字1
findViewById(R.id.btn_two).setOnClickListener(this); // 数字2
findViewById(R.id.btn_three).setOnClickListener(this); // 数字3
findViewById(R.id.ib_left).setOnClickListener(this); // (
findViewById(R.id.btn_zero).setOnClickListener(this); // 数字0
findViewById(R.id.btn_dot).setOnClickListener(this); // “小数点”
findViewById(R.id.btn_equal).setOnClickListener(this); // “等号”
findViewById(R.id.ib_right).setOnClickListener(this); // )
}
@Override
public void onClick(View v) {
String inputText;
inputText = ((TextView) v).getText().toString();
Log.d(TAG, "inputText=" + inputText);
if (v.getId() == R.id.btn_clear) { // 点击了清除按钮
clear();
}
else if (v.getId() == R.id.btn_cancel) { // 点击了取消按钮
refreshText(showText.substring(0, showText.length() - 1));
}
else if (v.getId() == R.id.btn_plus || v.getId() == R.id.btn_minus || v.getId() == R.id.btn_multiply || v.getId() == R.id.btn_divide) { // +-*/
operator = inputText;
refreshText(showText + operator);
}
else if (v.getId() == R.id.btn_equal) { // 等号逻辑 ===================
num.clear();
op.clear();
calculate(String.valueOf(showText));
refreshText(showText);
}
else if (v.getId() == R.id.ib_left) { // (
refreshText(showText + "(");
}
else if (v.getId() == R.id.ib_right) { // )
refreshText(showText + ")");
}
else { // 点击了其他按钮，包括数字和小数点
refreshText(showText + inputText);
}
}
private void eval() {
Double a = num.peek(); num.pop();
Double b = num.peek(); num.pop();
Character p = op.peek(); op.pop();
Double r = 0.0;
if(p == '+') r = b + a;
if(p == '-') r = b - a;
if(p == '*') r = b * a;
if(p == '/') r = b / a;
num.push(r);
}
private void calculate(String expression) {
while(!num.empty()) num.pop();
while(!op.empty()) op.pop();
// System.out.println(expression);
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (Character.isDigit(c) || c == '.') {
Double x = 0.0, k = 0.1;
int j = i, z = 0;
while (j < expression.length() && (Character.isDigit(expression.charAt(j)) || expression.charAt(j) == '.')) {
if(z == 1) {
x = x + k * (expression.charAt(j) - '0') * k;
k *= 0.1;
}
if(expression.charAt(j) == '.') {
z = 1;
}
if(z == 0) x = x * 10 + (expression.charAt(j) - '0');
j++;
}
i = j - 1;
num.push(x);
} else if (c == '(') {
op.push(c);
} else if (c == ')') {
while (op.peek() != '(') eval();
op.pop();
} else {
while (op.size() > 0 && priority[op.peek()] >= priority[c]) eval();
op.push(c);
}
}
// System.out.println(num.size());
while (op.size() > 0) eval();
if (!num.isEmpty()) {
result = String.valueOf(num.pop());
refreshText(result);
}
System.out.println(result);
}
private void refreshText(String text) {
showText = text;
tv_result.setText(showText);
}
private void clear() {
num.clear();
op.clear();
refreshOperate("");
refreshText("");
}
// 刷新运算结果
private void refreshOperate(String new_result) {
result = new_result;
operator = "";
}
}
MainActivity3——CODE：
package com.example.algoritmcalculator;
import android.annotation.SuppressLint;
import android.os.Bundle;
import android.util.Log;
import android.view.View;
import android.widget.TextView;
import android.widget.Toast;
import androidx.activity.EdgeToEdge;
import androidx.appcompat.app.AppCompatActivity;
import androidx.core.graphics.Insets;
import androidx.core.view.ViewCompat;
import androidx.core.view.WindowInsetsCompat;
import java.util.Scanner;
public class MainActivity3 extends AppCompatActivity implements View.OnClickListener {
private final static String TAG = "CalculatorActivity";
private TextView tv_result; // 声明一个文本视图对象
private int operator = 0; // 运算符
private int firstNum = 0; // 第一个操作数
private int secondNum = 0; // 第二个操作数
private int thirdNum = 0; // 第三个操作数
private int res = 0;
private String result = ""; // 当前的计算结果
private String showText = ""; // 显示的文本内容
@SuppressLint("MissingInflatedId")
@Override
protected void onCreate(Bundle savedInstanceState) {
super.onCreate(savedInstanceState);
EdgeToEdge.enable(this);
setContentView(R.layout.activity_main3);
ViewCompat.setOnApplyWindowInsetsListener(findViewById(R.id.main3), (v, insets) -> {
Insets systemBars = insets.getInsets(WindowInsetsCompat.Type.systemBars());
v.setPadding(systemBars.left, systemBars.top, systemBars.right, systemBars.bottom);
return insets;
});
findViewById(R.id.one).setOnClickListener(this); // 数字1
findViewById(R.id.two).setOnClickListener(this); // 数字2
findViewById(R.id.three).setOnClickListener(this); // 数字3
findViewById(R.id.four).setOnClickListener(this); // 数字4
findViewById(R.id.five).setOnClickListener(this); // 数字5
findViewById(R.id.six).setOnClickListener(this); // 数字6
findViewById(R.id.seven).setOnClickListener(this); // 数字7
findViewById(R.id.eight).setOnClickListener(this); // 数字8
findViewById(R.id.nine).setOnClickListener(this); // 数字9
findViewById(R.id.zero).setOnClickListener(this); // 数字0
findViewById(R.id.pow).setOnClickListener(this);
findViewById(R.id.pow_modify).setOnClickListener(this);
findViewById(R.id.is_prime).setOnClickListener(this);
findViewById(R.id.get_prime).setOnClickListener(this);
findViewById(R.id.gcd).setOnClickListener(this);
findViewById(R.id.lcm).setOnClickListener(this);
findViewById(R.id.gauss).setOnClickListener(this);
findViewById(R.id.phi).setOnClickListener(this);
findViewById(R.id.exgcd).setOnClickListener(this);
findViewById(R.id.equal).setOnClickListener(this);
findViewById(R.id.space).setOnClickListener(this);
findViewById(R.id.clear).setOnClickListener(this);
findViewById(R.id.cancel).setOnClickListener(this);
tv_result = findViewById(R.id.textView2);
}
@Override
public void onClick(View v) {
String inputText;
inputText = ((TextView) v).getText().toString();
Log.d(TAG, "inputText=" + inputText);
if (v.getId() == R.id.clear) { // 点击了C按钮
clear();
}
else if (v.getId() == R.id.cancel) { // 点击了取消按钮
refreshText(showText.substring(0, showText.length() - 1));
}
else if(v.getId() == R.id.equal) {
calculate(String.valueOf(showText));
refreshText(showText);
}
else if(v.getId() == R.id.pow) operator = 1;
else if(v.getId() == R.id.pow_modify) operator = 2;
else if(v.getId() == R.id.is_prime) operator = 3;
else if(v.getId() == R.id.get_prime) operator = 4;
else if(v.getId() == R.id.gcd) operator = 5;
else if(v.getId() == R.id.lcm) operator = 6;
else if(v.getId() == R.id.gauss) operator = 7;
else if(v.getId() == R.id.phi) operator = 8;
else if(v.getId() == R.id.exgcd) operator = 9;
else if(v.getId() == R.id.linear) operator = 10;
else { // 点击了其他按钮，包括数字和小数点
refreshText(showText + inputText);
}
// refreshText(showText + inputText);
}
private void calculate(String expression) {
int z = 0;
for (int i = 0; i < expression.length(); i++) {
char c = expression.charAt(i);
if (Character.isDigit(c)) {
int x = 0;
int j = i;
while (j < expression.length() && Character.isDigit(expression.charAt(j))) {
x = x * 10 + (expression.charAt(j) - '0');
j++;
}
i = j - 1;
if(z == 0) {
firstNum = x;
z = 1;
}
else if(z == 1) {
secondNum = x;
z = 2;
}
else {
thirdNum = x;
z = 0;
}
}
}
switch(operator) {
case 1:
res = MathUtils.qmi(firstNum, secondNum);
break;
case 2:
res = MathUtils.qm(firstNum, secondNum, thirdNum);
break;
case 3:
boolean isPrime = MathUtils.is_prime(firstNum);
result = isPrime ? "Prime" : "Not Prime";
break;
case 4:
MathUtils.get_prime(firstNum);
// Assuming you want to display the primes in some way
StringBuilder primesBuilder = new StringBuilder();
for (int j = 0; j < MathUtils.cnt; j++) {
primesBuilder.append(MathUtils.primes[j]).append(" ");
}
result = primesBuilder.toString();
break;
case 5:
res = MathUtils.gcd(firstNum, secondNum);
break;
case 6:
res = MathUtils.lcm(firstNum, secondNum);
break;
// case 7: gauss function is not implemented
case 8:
res = MathUtils.phi(firstNum);
break;
case 9: {
int[] x = new int[1];
int[] y = new int[1];
MathUtils.exgcd(firstNum, secondNum, x, y);
res = x[0]; // or y[0] depending on what you want to return
break;
}
case 10: {
int[] x = new int[1];
int[] y = new int[1];
long d = MathUtils.linear(firstNum, secondNum, x, y);
res = (int)d; // or x[0] or y[0] depending on what you want to return
break;
}
default:
Toast.makeText(this, "Invalid operation", Toast.LENGTH_SHORT).show();
return;
}
// Display the result
if (operator != 3 && operator != 4 && operator != 10 && operator != 9) {
result = String.valueOf(res);
}
refreshText(result);
}
// 刷新文本显示
private void refreshText(String text) {
showText = text;
CharSequence t = showText;
Log.d(TAG, "t=" + t);
tv_result.setText(t);
}
// 清空并初始化
private void clear() {
//refreshOperate("");
refreshText("");
}
}
MathUtils——CODE：
package com.example.algoritmcalculator;
public class MathUtils {
public static boolean[] st = new boolean[100000];
public static int[] primes = new int[100000];
public static int cnt;
public static int qmi(int a, int k) {
int res = 1;
while (k != 0) {
if ((k & 1) != 0) res = res * a;
k >>>= 1; // 使用无符号右移，确保位移操作的正确性
a = a * a; // 将a扩大平方倍
}
return res;
}
public static int qm(int a, int b, int p) {
int res = 1;
while (b != 0) {
if ((b & 1) != 0) res = (res * a) % p;
a = (a * a) % p;
b >>= 1;
}
return res;
}
public static boolean is_prime(int x) {
if (x < 2) return false;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) return false;
}
return true;
}
public static void get_prime(int n) {
for (int i = 2; i <= n; i++) {
if (!st[i]) primes[cnt++] = i;
for (int j = 0; primes[j] <= n / i; j++) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
public static int gcd(int a, int b) {
return b != 0 ? gcd(b, a % b) : a;
}
public static int lcm(int a, int b) {
return a * b / gcd(a, b);
}
public static int gauss() {
// 此函数需要一个具体的矩阵a和精度eps来执行高斯消元
// 由于没有提供具体的矩阵和eps值，这里不实现该函数
return 0;
}
public static int phi(int x) {
int res = x;
for (int i = 2; i <= x / i; i++) {
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
}
if (x > 1) res = res / x * (x - 1);
return res;
}
public static void exgcd(int a, int b, int[] x, int[] y) {
if (b == 0) {
x[0] = 1;
y[0] = 0;
return;
}
int aa = a, bb = b;
MathUtils.exgcd(bb, aa % bb, y, x);
y[0] = y[0] - (a / b) * x[0];
}
public static int linear(int a, int b, int[] x, int[] y) {
if (b == 0) {
x[0] = 1;
y[0] = 0;
return a;
}
int d = MathUtils.linear(b, a % b, y, x);
y[0] -= a / b * x[0];
return d;
}
}
activity_main.xml:
<?xml version="1.0" encoding="utf-8"?>
<androidx.constraintlayout.widget.ConstraintLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/main"
android:layout_width="match_parent"
android:layout_height="match_parent"
tools:context=".MainActivity">
<androidx.constraintlayout.widget.Group
android:id="@+id/group"
android:layout_width="wrap_content"
android:layout_height="wrap_content" />
<LinearLayout
android:layout_width="match_parent"
android:layout_height="match_parent"
android:orientation="vertical"
android:gravity="center_horizontal"
android:background="#2CC0F1"
>
<TextView
android:id="@+id/textView"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:text="计算器"
android:textSize="60dp"
tools:layout_editor_absoluteX="50dp"
tools:layout_editor_absoluteY="15dp" />
<Button
android:id="@+id/button"
android:layout_width="300dp"
android:layout_height="120dp"
android:layout_marginTop="50sp"
android:text="普通计算器"
android:background="#8ed1c0"
android:textSize="30sp"
tools:layout_editor_absoluteX="84dp"
tools:layout_editor_absoluteY="372dp" />
<Button
android:id="@+id/button2"
android:layout_width="300dp"
android:layout_height="120dp"
android:text="算法计算器"
android:background="#ce8ed1"
android:textSize="30sp"
android:layout_marginTop="50sp"
tools:layout_editor_absoluteX="84dp"
tools:layout_editor_absoluteY="213dp" />
</LinearLayout>
</androidx.constraintlayout.widget.ConstraintLayout>
activity_main2.xml:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/main2"
android:layout_width="match_parent"
android:layout_height="match_parent"
tools:context=".MainActivity2"
android:background="#eeeeee"
android:orientation="vertical"
android:padding="5dp">
<ScrollView
android:layout_width="match_parent"
android:layout_height="wrap_content">
<LinearLayout
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:orientation="vertical">
<TextView
android:layout_width="360dp"
android:layout_height="wrap_content"
android:gravity="center"
android:text="计算器"
android:textColor="#000000"
android:textSize="20sp" />
<LinearLayout
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:orientation="vertical">
<TextView
android:id="@+id/tv_result"
android:layout_width="360dp"
android:layout_height="wrap_content"
android:background="#ffffff"
android:gravity="right|bottom"
android:lines="3"
android:maxLines="3"
android:scrollbars="vertical"
android:text="0"
android:textColor="#000000"
android:textSize="25sp" />
</LinearLayout>
<GridLayout
android:layout_width="match_parent"
android:layout_height="wrap_content"
android:columnCount="4">
<Button
android:id="@+id/btn_cancel"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="CE"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_divide"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="/"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_multiply"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="*"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_clear"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="C"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_seven"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="7"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_eight"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="8"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_nine"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="9"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_plus"
android:layout_width="wrap_content"
android:layout_height="wrap_content"
android:gravity="center"
android:text="+"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_four"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="4"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_five"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="5"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_six"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="6"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_minus"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="-"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_one"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="1"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_two"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="2"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_three"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="3"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_equal"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="="
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_dot"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="."
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/btn_zero"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="0"
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/ib_left"
android:layout_width="90dp"
android:layout_height="75dp"
android:gravity="center"
android:text="("
android:textColor="@color/black"
android:textSize="30sp" />
<Button
android:id="@+id/ib_right"
android:layout_width="89dp"
android:layout_height="75dp"
android:gravity="center"
android:text=")"
android:textColor="@color/black"
android:textSize="30sp" />
</GridLayout>
</LinearLayout>
</ScrollView>
</LinearLayout>
activity_main3.xml:
<?xml version="1.0" encoding="utf-8"?>
<LinearLayout xmlns:android="http://schemas.android.com/apk/res/android"
xmlns:app="http://schemas.android.com/apk/res-auto"
xmlns:tools="http://schemas.android.com/tools"
android:id="@+id/main3"
android:layout_width="match_parent"
android:layout_height="match_parent"
android:orientation="vertical"
tools:context=".MainActivity3">
<TextView
android:id="@+id/textView2"
android:layout_width="match_parent"
android:layout_height="111dp"
android:textSize="30sp"
android:layout_margin="10sp"
android:text="TextView" />
<GridLayout
android:layout_width="match_parent"
android:layout_height="550sp"
android:columnCount="4"
android:layout_margin="10sp"
android:rowCount="5">
<Button
android:id="@+id/pow"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_margin="5sp"
android:layout_columnWeight="1"
android:background="#FFB1CD"
android:text="pow" />
<Button
android:id="@+id/pow_modify"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_margin="5sp"
android:layout_columnWeight="1"
android:background="#FFB1CD"
android:text="pow_modify" />
<Button
android:id="@+id/is_prime"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_margin="5sp"
android:layout_columnWeight="1"
android:background="#FFB1CD"
android:text="is_prime" />
<Button
android:id="@+id/get_prime"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:background="#FFB1CD"
android:text="get_prime" />
<Button
android:id="@+id/gcd"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:layout_margin="5sp"
android:background="#FFB1CD"
android:text="gcd" />
<Button
android:id="@+id/lcm"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:layout_margin="5sp"
android:background="#FFB1CD"
android:text="lcm" />
<Button
android:id="@+id/gauss"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:layout_margin="5sp"
android:background="#FFB1CD"
android:text="gauss" />
<Button
android:id="@+id/phi"
android:layout_width="0dp"
android:layout_height="0dp"
android:background="#FFB1CD"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:layout_margin="5sp"
android:text="phi" />
<Button
android:id="@+id/exgcd"
android:layout_width="0dp"
android:background="#FFB1CD"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="exgcd" />
<Button
android:id="@+id/linear"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#FFB1CD"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="linear" />
<Button
android:id="@+id/cancel"
android:layout_width="0dp"
android:layout_height="0dp"
android:background="#95A3F7"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="CE" />
<Button
android:id="@+id/clear"
android:layout_width="0dp"
android:background="#95A3F7"
android:layout_margin="5sp"
android:layout_height="0dp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="C" />
<Button
android:id="@+id/one"
android:layout_width="0dp"
android:background="#8ebed1"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="1" />
<Button
android:id="@+id/two"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:background="#8ebed1"
android:text="2" />
<Button
android:id="@+id/three"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:background="#8ebed1"
android:layout_columnWeight="1"
android:text="3" />
<Button
android:id="@+id/zero"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:background="#8ebed1"
android:layout_columnWeight="1"
android:text="0" />
<Button
android:id="@+id/four"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#8ebed1"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="4" />
<Button
android:id="@+id/five"
android:layout_width="0sp"
android:layout_height="0sp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:background="#8ebed1"
android:layout_columnWeight="1"
android:text="5" />
<Button
android:id="@+id/six"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#8ebed1"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="6" />
<Button
android:id="@+id/space"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#8ebed1"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text=" " />
<Button
android:id="@+id/seven"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#8ebed1"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="7" />
<Button
android:id="@+id/eight"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#8ebed1"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="8" />
<Button
android:id="@+id/nine"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:layout_rowWeight="1"
android:background="#8ebed1"
android:layout_columnWeight="1"
android:text="9" />
<Button
android:id="@+id/equal"
android:layout_width="0dp"
android:layout_height="0dp"
android:layout_margin="5sp"
android:background="#d1908e"
android:layout_rowWeight="1"
android:layout_columnWeight="1"
android:text="=" />
</GridLayout>
</LinearLayout>
算法实现
详情函数都是c++代码块，Java代码见上文数学类
POW：
输入：两个整数，空格隔开（底数， 指数）
点击POW按钮后按等号计算（其余函数不再赘述）
读入底数和指数，通过快速幂算法求出值
bool is_prime(int x){
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++ ){
if(x % i == 0) return false;
}
return true;
}
POW_MODIFY:
输入：三个整数，空格隔开（底数，指数，求余mod）
逆元：除以一个数求余等于乘上这个逆元再求余
【由于求余法则中没有除法的规定，我们只能通过逆元来求余】
乘法逆元的定义
若整数 b，m 互质，并且对于任意的整数 a，如果满足 b|a，则存在一个整数 x，使得 a/b≡a×x(mod m)，则称 x 为 b 的模 m 乘法逆元，记为 b−1(mod m)。
b 存在乘法逆元的充要条件是 b 与模数 m 互质。当模数 m 为质数时，b^m−2即为 b 的乘法逆元。
由此可知，求逆元的方式同快速幂，只需要将指数改为p-2即可
ll qm(ll a, ll b, ll p)
{
ll res = 1;
while(b)
{
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
IS_PRIME:
输入：一个整数（判断是否为质数）
输入一个数，判断是否为质数，质数返回√，非质数返回×
bool is_prime(int x){
if(x < 2) return false;
for(int i = 2; i <= x / i; i ++ ){
if(x % i == 0) return false;
}
return true;
}
GET_PRIME:
输入：一个整数（输出小于它的所有质数）
输入一个数，筛出1~n中的质数，输出为数组，采用线性筛
bool st[N];
int primes[N], cnt;
void get_prime(int n){
for(int i = 2; i <= n; i++){
if(!st[i]) primes[cnt ++ ] = i;
for(int j = 0; primes[j] <= n / i; j ++ ){
st[primes[j] * i] = true;
if(i % primes[j] == 0) break;
}
}
}
GCD:
输入：两个整数（输出其最大公约数）
输入两个数，输出最大公约数，采用辗转相除法
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a; // 辗转相除法
}
LCM:
输入：两个整数（输出其最小公倍数）
输入两个数，输出最小公倍数
int lcm(int a, int b) {
return a * b / gcd(a, b);
}
GAUSS:
输入：一个n，接下来n行代表着输入的未知数常数（输出为各个未知数）
输入常数，输出所有xi的值
int gauss() // 高斯消元
{
int c, r;
for(c = 0, r = 0; c < n; c ++ )
{
int t = r;
for(int i = r; i < n; i ++ ) // 找出绝对值最大的行
{
if(fabs(a[i][c]) > fabs(a[t][c])) t = i;
}
if(fabs(a[t][c]) < eps) continue;
for(int i = c; i <= n; i ++ ) swap(a[t][i], a[r][i]); // 将绝对值最大的行换到最顶端
for(int i = n; i >= c; i -- ) a[r][i] /= a[r][c]; // 将当前行的首位变成1
for(int i = r + 1; i < n; i ++ ) // 用当前行将下面所有的列消成0
{
if(fabs(a[i][c]) > eps)
{
for(int j = n; j >= c; j -- )
{
a[i][j] -= a[r][j] * a[i][c];
}
}
}
r ++ ;
}
if(r < n)
{
for(int i = r; i < n; i ++ )
{
if(fabs(a[i][n]) > eps) return 2; // 无解，即b不为0
}
return 1; // 有无穷多组解
}
for(int i = n - 1; i >= 0; i -- )
{
for(int j = i + 1; j < n; j ++ )
{
a[i][n] -= a[i][j] * a[j][n];
}
}
return 0;
}
PHI:
输入：一个整数（输出其欧拉函数）
欧拉函数：1~N中与N互质的数的个数被称为欧拉函数，记为 ϕ(N)。
公式： phi = 质数分之质数-1之积
思路： 通过试除法找到质数，然后套用公式
int phi(int x) {
int res = x;
for(int i = 2; i <= x / i; i++) {
if(x % i == 0) {
res = res / i * (i - 1);
while(x % i == 0) x /= i;
}
}
if(x > 1) res = res / x * (x - 1);
return res;
}
EXGCD:
输入：两个整数a,b（输出为x，y的值）
扩展欧几里得算法：求出一组x,y，使得a * x + b * y == gcd(a, b)
void exgcd(int a, int b, int &x, int &y) {
if(!b) {
x = 1, y = 0;
return ;
}
exgcd(b, a % b, y, x);
y = y - a / b * x;
}
LINEAR：
输入：两个整数a,b（输出x)
线性同余方程：求一个x，满足a * x == b(mod m)
#include<iostream>
#include<algorithm>
using namespace std;
typedef long long ll;
ll linear(ll a, ll b, ll &x, ll &y)
{
if(!b)
{
x = 1, y = 0; // 边界，（或理解为递归的重点）
return a;
}
int d = linear(b, a % b, y, x);// y与b对应，x与a对应
y -= a / b * x;// 公式推导
return d;
}
int main()
{
int n;
cin >> n;
while(n -- )
{
ll a, b, m;
cin >> a >> b >> m;
ll x, y;
ll t = linear(a, m, x, y);
if(b % t) puts("impossible");
else cout << x * (b / t) % m << endl;
}
return 0;
}