# 因數

（重定向自因子

## 定义

${\displaystyle a,b}$  满足 ${\displaystyle a\in \mathbb {N} ^{*},b\in \mathbb {N} }$ . 若存在 ${\displaystyle q\in \mathbb {N} }$  使得 ${\displaystyle b=aq}$ , 那么就说 ${\displaystyle b}$ ${\displaystyle a}$ 倍数${\displaystyle a}$ ${\displaystyle b}$ 约数。这种关系记作 ${\displaystyle a|b}$ ,读作“${\displaystyle a}$  整除 ${\displaystyle b}$ ”.

## 性质

• ${\displaystyle a|b,\;b|c}$  那么 ${\displaystyle a|c}$ .
• ${\displaystyle a|b,\;a|c}$ ${\displaystyle x,y\in \mathbb {Z} }$ , 有 ${\displaystyle a|(bx+cy)}$ .
• ${\displaystyle a|b}$ , 设 ${\displaystyle t\not =0}$ , 那么 ${\displaystyle (ta)|(tb)}$ .
• ${\displaystyle b=qd+c}$ , 那么 ${\displaystyle d|b}$ 充要条件${\displaystyle d|c}$
• ${\displaystyle x,y\in \mathbb {Z} }$  满足 ${\displaystyle ax+by=1,\;a|n.\;b|n}$  那么 ${\displaystyle ab|n}$ .

${\displaystyle \because a|n,\;b|n\quad \therefore ab|bn,\;ab|an\quad \therefore ab|(anx+bny)}$

${\displaystyle \because ax+by=1\quad \therefore ab|n}$

## 相关定理

### 整数的唯一分解定理

${\displaystyle A=\prod _{i=1}^{n}p_{i}^{a_{i}}}$ , 其中 ${\displaystyle p_{i}}$  是一个素数.

### 因数个数

${\displaystyle N}$  唯一分解为 ${\displaystyle N=p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times p_{3}^{a_{3}}\times \cdots \times p_{n}^{a_{n}}=\prod _{i=1}^{n}p_{i}^{k_{i}}}$ , 则 ${\displaystyle d(N)=(a_{1}+1)\times (a_{2}+1)\times (a_{3}+1)\times \cdots \times (a_{n}+1)=\prod _{i=1}^{n}\left(a_{i}+1\right)}$ .

### 因数和

${\displaystyle N}$  唯一分解为 ${\displaystyle N=p_{1}^{a_{1}}\times p_{2}^{a_{2}}\times p_{3}^{a_{3}}\times \cdots \times p_{n}^{a_{n}}=\prod _{i=1}^{n}p_{i}^{k_{i}}}$ , 则 ${\displaystyle \sigma (N)=\prod _{i=1}^{n}\left(\sum _{j=0}^{a_{i}}p_{i}^{j}\right)}$ .

{\displaystyle {\begin{aligned}\sigma (N)&={\frac {p_{1}^{a_{1}+1}-1}{p_{1}-1}}\times {\frac {p_{2}^{a_{2}+1}-1}{p_{2}-1}}\times \cdots \times {\frac {p_{n}^{a_{n}+1}-1}{p_{n}-1}}&\end{aligned}}}

{\displaystyle {\begin{aligned}\sigma (2646)&=(1+2)\times (1+3+9+27)\times (1+7+49)\\&={\frac {2^{2}-1}{2-1}}\times {\frac {3^{4}-1}{3-1}}\times {\frac {7^{3}-1}{7-1}}\\&=3\times 40\times 57\\&=6840\end{aligned}}}

## 其他

• 1是所有整數的正因數，-1是所有整數的負因數，因為${\displaystyle x=1x=-1\times (-x)}$

• 質數${\displaystyle p}$ 只有2個正因數：1, ${\displaystyle p}$ ${\displaystyle p}$ 平方數只有三個正因數：1, ${\displaystyle p}$ , ${\displaystyle p^{2}}$

## 程式參考

### 给定整数的所有因数

#### C語言

#include <stdio.h>
#include <stdlib.h>
int main(void)
{
int n=0,i;
printf("請輸入一個正整數Ｎ:");
scanf("%d",&n);
for(i=1;i<=n;i++)
{
if(n%i==0)printf("%d \n",i);
}
system("pause");
return 0;
}


### ${\displaystyle A^{B}}$  的因数和

#### C++

#include<bits/stdc++.h>

constexpr auto mod = 2147483648LL;
long int a, b;
long long n[10001], p[10001];

template<typename T>
T Prid(T a, T b) {
T sum = 1;
for (; b > 0; b >>= 1) {
if (b & 1)sum = sum * a%mod;
a = a * a%mod;
}
return sum;
}

template<typename T>
T Get_Sum(T p, T n) {
if (n == 0)return 1;
if (n & 1)return (Get_Sum(p, (n >> 1))*(1 + Prid(p, (n >> 1) + 1))) % mod;
else return (Get_Sum(p, (n >> 1) - 1)*(1 + Prid(p, (n >> 1) + 1)) + Prid(p, (n >> 1))) % mod;
}

int main()
{
std::cin >> a >> b;
unsigned int nowAt = 0;

for (int i = 2; i*i <= a; i += (i == 2 ? 1 : 2))
if (a%i == 0) {
p[nowAt] = i;
n[nowAt] = 0;
while (a%i == 0) { ++n[nowAt]; a /= i; }
++nowAt;
}
if (a != 1) {
p[nowAt] = a; n[nowAt++] = 1;
}

long long ans = 1;
for (int i = 0; i < nowAt; i++)
ans = (ans*Get_Sum(p[i], n[i] * b)) % mod;

std::cout << ans << std::endl;

system("pause");
return 0;
}


#### C#

using System;
namespace DS
{
class Program
{
public static class Global
{
public static readonly Int64 mod = 2147483648;
}

static void Main(string[] args)
{
Int64 a = Convert.ToInt64(div[0]), b = Convert.ToInt64(div[1]);
uint nowAt = 0;

Int64[] p = new Int64[10001], n = new Int64[10001];

for (int i = 2; i * i <= a; i += (i == 2 ? 1 : 2))
if (a % i == 0)
{
p[nowAt] = i;
n[nowAt] = 0;
while (a % i == 0) { ++n[nowAt]; a /= i; }
++nowAt;
}
if (a != 1)
{
p[nowAt] = a; n[nowAt++] = 1;
}

Int64 ans = 1;
for (int i = 0; i < nowAt; i++)
ans = (ans * Get_Sum(p[i], n[i] * b)) % Global.mod;

Console.WriteLine(ans.ToString());
}

static Int64 Prid(Int64 a,Int64 b)
{
Int64 sum = 1;
for (; b > 0; b >>= 1)
{
if ((b & 1) == 1) sum = sum * a % Global.mod;
a = a * a % Global.mod;
}return sum;
}

static Int64 Get_Sum(Int64 p,Int64 n)
{
if (n == 0) return 1;
if ((n & 1) == 1) return (Get_Sum(p, (n >> 1)) * (1 + Prid(p, (n >> 1) + 1))) % Global.mod;
else return (Get_Sum(p, (n >> 1) - 1) * (1 + Prid(p, (n >> 1) + 1)) + Prid(p, (n >> 1))) % Global.mod;
}
}
}