一些笔记 | 质因子

区间筛

给定区间[L，R](L≤R≤2147483647,R-L≤1000000)，请计算区间中素数的个数。

原理 : 对于每一个合数 \(x\) , 都至少有一个质因子 \(\le \sqrt{x}\)
先筛出 [1,\(\sqrt{max\ int}\)] 内的质数 ,
再用筛出的质数对 \([L,R]\) 进行质数筛

code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
int n, N, x, pri[10000];
typedef long long LL;
bool a[maxn];
int Eratosthenes_Sieve(int n, int pri[])
{
  for (int i = 2; i * i <= n; i++)
      if (a[i] == 0)
          for (int j = i << 1; j <= n; j += i)
              a[j] = 1;
  int cnt = 0;
  for (int i = 2; i <= n; i++)
      if (!a[i])
          pri[cnt++] = i;
  return cnt;
}
int main()
{
  int cnt = Eratosthenes_Sieve(50000, pri);
  LL L, R;
  scanf("%lld %lld", &L, &R);
  memset(a, 0, sizeof(a));
  for (int i = 0; i < cnt; i++)
      for (LL j = max(2ll, (L - 1) / pri[i] + 1) * pri[i] ; j <= R; j += pri[i])
          a[j - L] = 1;
  int ans = 0;
  for (LL i = L; i <= R; i++)
      if (a[i - L] == 0)
          ans++;
  printf("%d", ans);
  return 0;
}

P3601

给定区间 \([l,r]\) , 求 \(\sum\limits_{x=l}^{r} x-\phi(x)\) \(r-l\le 1e6\) , \(l,r \in[1,1e12]\)
有二性质:

\(\phi(x) = x\times \prod\limits_{i=1}^{x}{\frac{p_i-1}{p_i}}\)
对于一个合数\(x\) ,至多存在一个质因子 , \(\ge \sqrt{x}\)

则可以筛出 \([1,\sqrt{1e12}]\) 内的质数
然后用这些质数对 \([l,r]\) 内进行操作
\(x\) 的一质因子\(p_i\) 对 \(\phi (x)\) 的贡献为 \(\frac{p_i-1}{p_i}\)
并特判 \(\ge \sqrt{x}\) 的至多一个质因子即可

code:

#include <bits/stdc++.h>
using namespace std;
#define maxn 1000010
#define mod 666623333
int n, N, pri[maxn];
typedef long long LL;
bool a[maxn];
LL phi[maxn], K[maxn];
int Eratosthenes_Sieve(int n, int pri[])
{
  for (int i = 2; i * i <= n; i++)
      if (a[i] == 0)
          for (int j = i << 1; j <= n; j += i)
              a[j] = 1;
  int cnt = 0;
  for (int i = 2; i <= n; i++)
      if (!a[i])
          pri[cnt++] = i;
  return cnt;
}
int main()
{
  int cnt = Eratosthenes_Sieve(1000000, pri);
  LL L, R, ans = 0;
  scanf("%lld %lld", &L, &R);
  for (LL i = L; i <= R; i++)
      phi[i - L] = K[i - L] = i;
  for (int i = 0; i < cnt; i++)
      for (LL p = pri[i], j = max(2ll, (L - 1) / p + 1) * p; j <= R; j += p)
      {
          LL x = j - L;
          phi[x] = phi[x] / p * (p - 1);
          for (; K[x] % p == 0;)
              K[x] /= p;
      }
  for (LL i = L; i <= R; (ans += i - phi[i - L]) %= mod, i++)
      if (K[i - L] != 1)
          phi[i - L] = phi[i - L] / K[i - L] * (K[i - L] - 1);
  printf("%lld", ans);
  return 0;
}

UOJ #48

发现一性质:
\(x = \prod\limits{p_i^{a^i}},y = \prod\limits{p_i^{b^i}},\gcd{(x,y)} =\prod\limits{p_i^{\min(a_i,b_i)}}\Rightarrow sgcd|gcd\)
则: \(sgcd(x,y)=\frac{gcd}{min\{p_i|p_i:gcd\}}\)
因为 \(a_1\) 一直出现 ,
则 \(p_i |gcd\Rightarrow p_i|a_1\)
则可以预处理\(a_1\) 的质因子 , 并使用 \(a_1\) 的质因子进行试除
\(\gcd = 1\)时 , \(sgcd = -1\)

code:

#include <bits/stdc++.h>
#define maxn 50
using namespace std;
typedef long long LL;
#define G c = getchar()
inline LL read()
{
  LL x = 0, f = 1;
  char G;
  while (c > 57 || c < 48)
  {
      if (c == '-')
          f = -1;
      G;
  }
  while (c > 47 && c < 58)
  {
      x = x * 10 + c - 48;
      G;
  }
  return x * f;
}
LL p[maxn], tot;
LL x, y, w;
LL gcd(LL x, LL y) { return y ? gcd(y, x % y) : x; }
int main()
{
  int n = read();
  y = x = read();
  for (LL i = 2; i * i <= x; i++)
      if (x % i == 0)
          for (p[tot++] = i; x % i == 0;)
              x /= i;
  if (x - 1)
      p[tot++] = x;
  printf("%lld ", tot ? y / p[0] : -1);
  for (int i = 2, j; i <= n; i++)
  {
      x = read();
      w = gcd(x, y);
      int f = 0;
      for (j = 0; j < tot; j++)
          if (w % p[j] == 0)
          {
              f = 1;
              break;
          }
      printf("%lld ", f ? w / p[j] : -1);
  }
  return 0;
}

不定方程

P4167
- 原式 = \((x-n!)(y-n!)=(n!)^2\)
  则设\(x=n!+a,y=n!+b\) , 有\(a\times b=(n!)^2\)
- 由一一对应关系可知 , 解的数目 = \((n!)^2\) 的约数个数
  若\(x = \prod\limits{p_i^{a^i}}\)
  由约数和定理可知, \(\alpha(x) = \prod\limits{(a_i+1)}\)
- \(n!\) 内的质因子小于 \(n\) , 则可以预处理出所有 \(\le n\) 的质数
  \(p_i\) 在 \(n!\) 中出现次数\(a_i=\sum\limits_{k=1}^{\inf}{\lfloor\frac{n}{p_i^k}\rfloor} (p_i^k\le n)\)(可以看做 \(p_i\) 进制数)
  套约数和公式即可

code:

#include <bits/stdc++.h>
#define maxn 1000010
#define mod 1000000007
using namespace std;
int prime[maxn], vis[maxn], tot, n;
long long ans = 1, tmp, x, y;
int main()
{
    for (int i = 2; i <= maxn; i++)
    {
        if (!vis[i])
            prime[tot++] = i;
        for (int j = 0; j < tot && prime[j] * i < maxn; j++)
        {
            vis[prime[j] * i] = 1;
            if (i % prime[j] == 0)
                break;
        }
    }
    scanf("%d", &n);
    for (int i = 0; prime[i] <= n; i++)
    {
        tmp = 0;
        x = n;
        y = prime[i];
        for (; x; x /= prime[i])
            tmp += x / y;
        ans = (ans * (tmp << 1 | 1) % mod) % mod;
    }
    printf("%d", ans);
}

同余

P2312
对于一个多项式 \(f(x)\) ,
\(f(x+p) \equiv f(x) \pmod{p}\)
则若 \(f(x) = 0\), 有 \(f(x)\%p =0\)
可以使用取模的方法判断是否为0