数学问题
1. 质数筛
- 埃氏筛
利用当前已经找到的素数，从后面的数中筛去当前素数的倍数，由预备知识一可知，当前素数已经是筛去数的质因子，如此下去能筛除所有之后的合数，是一种比较快的筛法
bool st[N]; //如果为true则被筛掉，不是质数
int prime[N], cnt; //prime用于记录质数
void getprime(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) //可以只筛出质数的倍数即可
{
prime[cnt++] = i;
for(int j = i + i; j <= n; j += i)
st[j] = true;
}
}
}
-
线性筛
和埃氏筛法的区别是对于每一个要筛除的数，欧拉筛法只筛除一次，而埃氏筛法会重复筛除，比如8和16同时被2和4筛去，推荐使用欧拉筛法，维护一个质数表
- 其中由于是从小到大枚举质数表，每个数一定被他的最小质因子筛掉
bool st[N]; //如果为true则被筛掉，不是质数
int prime[N], cnt; //prime用于记录质数
void getprime(int n)
{
for(int i = 2; i <= n; i++)
{
if(!st[i]) prime[cnt++] = i;
for(int j = 0; prime[j] <= n / i; j++)
{
st[prime[j] * i] = true;
if(i % prime[j] == 0) break;
}
}
}
2.最大公约数与最小公倍数
利用辗转相除法即欧几里得算法递归求解，最大公约数则为两数相乘后除最大公约数
int gcd(int a, int b)
{
return b ? gcd(b, a % b), a;
}
//或者
int gcd(int a, int b)
{
if(b == 0) return a;
else return gcd(b, a % b);
}
//或者
__gcd(a,b)
//最大公约数为
a * b / __gcd(a,b)
3.同余模定理
如对取模
typedef long long ll;
ll mod(ll n)
{
ll s = n
for(int i = 1; i < 5; i++)
{
s = ((s % 3) * (n % 3));
}
return s % 3
}
还有便是对大数进行取模，只能用字符串读入，利用进制转换时的数位分解进行求解
char s[1000];
int main()
{
int n;//模n
cin >> s;
cin >> n;
m = 0;
for(int i = 0; i < strlen(s); i++)
m = ((m * 10) % n + (s[i] - '0') % n) % n;
//也可以加完后再取模，但会超出范围
cout << n;
return 0;
}
