Visit of the Great

admin • 2022-01-12 08:21 • 人工智能

1.前言

真好玩，蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤蛤

2.题解

令

(

)

{

∣

∤

(

)

(

−

)

(

−

)

(

−

)

(

)

−

(

−

)

−

)

(

−

)

(

)

begin{aligned}令 G (x) = begin{cases} 1, 2 mid x \ 2, 2 nmid x end{cases}\gcd (k^{2^{i}} + 1, k^{2^{i + 1}} + 1) &= gcd (k^{2^{i}} + 1, k^{2^{i + 1}} - k^{2^{i}})\&= gcd (k^{2^{i}} + 1, k^{2^{i}} times (k^{2^{i}} - 1))\&= gcd (k^{2^{i}} + 1, k^{2^{i}} - 1)\&= gcd ((k^{2^{i}} + 1) - (k^{2^{i}} - 1), k^{2^{i}} - 1)\&= gcd (2, k^{2^{i}} - 1)\&= G (k)end{aligned}

$令 G (x) = {1, 2 ∣ x 2, 2 ∤ x g c d (k^{2^{i}} + 1, k^{2^{i + 1}} + 1) = g c d (k^{2^{i}} + 1, k^{2^{i + 1}} - k^{2^{i}}) = g c d (k^{2^{i}} + 1, k^{2^{i}} \times (k^{2^{i}} - 1)) = g c d (k^{2^{i}} + 1, k^{2^{i}} - 1) = g c d ((k^{2^{i}} + 1) - (k^{2^{i}} - 1), k^{2^{i}} - 1) = g c d (2, k^{2^{i}} - 1) = G (k)$

(

)

(

−

(

)

(

−

)

(

)

(

−

)

(

−

(

)

(

−

)

(

)

(

)

(

−

(

)

(

−

)

(

−

)

(

)

(

)

(

)

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= lcm (lcm_{i = l}^{{r - 2}} (k^{2^{i}} + 1), frac{(k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{gcd (k^{2^{r - 1}} + 1, k^{2^{r}} + 1)} )\&= lcm (lcm_{i = l}^{{r - 2}} (k^{2^{i}} + 1), frac{(k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{G (k)} )\&= lcm (lcm_{i = l}^{{r - 3}} (k^{2^{i}} + 1), frac{(k^{2^{r - 2}} + 1) times (k^{2^{r - 1}} + 1) times (k^{2^{r}} + 1)}{G (k) times G (k)} ) \ &=... end{aligned}

$l c m_{i = l r} (k^{2^{i}} + 1) m o d p = l c m (l c m_{i = l r - 2} (k^{2^{i}} + 1), \frac{( k ^{2^{r - 1}} + 1 ) \times ( k ^{2^{r}} + 1 )}{g c d ( k ^{2^{r - 1}} + 1 , k ^{2^{r}} + 1 )}) = l c m (l c m_{i = l r - 2} (k^{2^{i}} + 1), \frac{( k ^{2^{r - 1}} + 1 ) \times ( k ^{2^{r}} + 1 )}{G ( k )}) = l c m (l c m_{i = l r - 3} (k^{2^{i}} + 1), \frac{( k ^{2^{r - 2}} + 1 ) \times ( k ^{2^{r - 1}} + 1 ) \times ( k ^{2^{r}} + 1 )}{G ( k ) \times G ( k )}) = . . .$

(

)

∏

(

)

(

)

−

∏

(

)

−

(

)

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= frac{prod_{i = l}^{r} (k^{2^{i}} + 1)}{G(K)^{r - l}} bmod p\&= frac{prod_{i = l}^{r} (k^{2^{i}} + 1)}{G^{r - l}(K)} bmod pend{aligned}

$l c m_{i = l r} (k^{2^{i}} + 1) m o d p = \frac{\prod _{i = l r} ( k ^{2^{i}} + 1 )}{G ( K ) ^{r - l}} m o d p = \frac{\prod _{i = l r} ( k ^{2^{i}} + 1 )}{G ^{r - l} ( K )} m o d p$

发现这个小东西

∏

(

)

−

)

prod_{i = l}^{r} ((k^{2^{l}})^{i - l} + 1)

$\prod_{i = l r} ((k^{2^{l}})^{i - l} + 1)$ 就是

∑

−

(

)

sumlimits_{i = 0}^{r = 2^{r - l + 1} - 1} (k^{2^{l}})^i

$i = 0 \sum r = 2^{r - l + 1} - 1 (k^{2^{l}})^{i}$ (二进制拆分的唯一性)

(

)

−

begin{aligned} frac{(k^{2^{l}})^{2^{r - l + 1}} - 1}{k^{2^{l}} - 1}\= frac{k^{2^{r + 1}} - 1}{k^{2^{l}} - 1}end{aligned}

$\frac{( k ^{2^{l}} ) ^{2^{r - l + 1}} - 1}{k ^{2^{l}} - 1} = \frac{k ^{2^{r + 1}} - 1}{k ^{2^{l}} - 1}$

(

)

−

(

−

)

−

(

)

begin{aligned}mathrm{lcm}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= frac{k^{2^{r + 1}} - 1}{(k^{2^{l}} - 1) times G^{r - l}(K)}end{aligned}

$l c m_{i = l r} (k^{2^{i}} + 1) m o d p = \frac{k ^{2^{r + 1}} - 1}{( k ^{2^{l}} - 1 ) \times G ^{r - l} ( K )}$

然后有一个很？？的？？特判，

k bmod p == 0

$k m o d p = = 0$ 时要搞很多奇怪的东西，去？好了。

因为当

k bmod p == 0

$k m o d p = = 0$ 时，

(

−

)

2^{r + 1} bmod (p - 1)

$2^{r + 1} m o d (p - 1)$ 如果为零，则它会算出来一个

k ^ 0 bmod p = 1

$k^{0} m o d p = 1$ ，所以不对，这时候改为返回值为

$0$ 就好了。

#include <cmath>
#include <queue>
#include <vector>
#include <cstdio>
#include <cstdlib> 
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
#define fi first
#define se second
#define db double
#define LL long long
#define ULL unsigned long long
#define PII pair <int, int>
#define MP(x,y) make_pair (x, y)
#define rep(i,j,k) for (int i = (j); i <= (k); ++i)
#define per(i,j,k) for (int i = (j); i >= (k); --i)

template <typename T> T Max (T x, T y) { return x > y ? x : y; }
template <typename T> T Min (T x, T y) { return x < y ? x : y; }
template <typename T> T Abs (T x) { return x > 0 ? x : -x; }
template <typename T>
void read (T &x) {
    x = 0; T f = 1;
    char ch = getchar ();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar ();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + ch - '0';
        ch = getchar ();
    }
    x *= f;
}
template <typename T, typename... Args>
void read (T &x, Args&... args) {
    read (x); read (args...);
}
char For_Print[25];
template <typename T>
void write (T x) {
    if (x == 0) { putchar ('0'); return; }
    if (x < 0) { putchar ('-'); x = -x; }
    int poi = 0;
    while (x) {
        For_Print[++poi] = x % 10 + '0';
        x /= 10;
    }
    while (poi) putchar (For_Print[poi--]);
}
template <typename T>
void print (T x, char ch) {
    write (x); putchar (ch);
}

const LL Mod = 1e9 + 7;

LL sqre (LL x) { return x * x % Mod; }
void del (LL &x, LL y) { ((x -= y) < 0) && (x += Mod); }
void add (LL &x, LL y) { ((x += y) >= Mod) && (x -= Mod); }

LL t, k, l, r, p;

LL quick_pow (LL x, LL y, LL M) {
    LL res = 1;
    while (y) {
        if (y & 1) res = (res * x) % M;
        x = (x * x) % M; y >>= 1;
    }
    return res;
}
LL inv (LL x, LL M) {
    return quick_pow (x, M - 2, M);
}
LL G (LL x) {
    return (x % 2 == 0 ? 1 : 2);
}
LL f (LL x) {
	return k % p == 0 ? 0 : quick_pow (k, quick_pow (2, x, p - 1), p);
}

int main () {
    // freopen ("D:\lihan\1.in", "r", stdin);
    // freopen ("D:\lihan\1.out", "w", stdout);
    read (t);
    while (t--) {
        read (k, l, r, p);
        
		if (p == 2) {
			printf ("%dn", (k % 2 == 1 ? 0 : 1));
			continue;
		}
		
        LL res = 0;
		if (f (l) == 1) {
			res = quick_pow (2, r - l + 1, p);
		}
		else {
			
//			printf ("f (r + 1) = %lld, f (l) = %lldn", f (r + 1), f (l));
			
			res = f (r + 1) - 1 + p;
			res = (res * inv (f (l) - 1 + p, p)) % p;
		}
		
//		cout << res << endl;
		
        res *= inv (quick_pow (G (k), r - l, p) % p, p);
        res = (res % p + p) % p;
        print (res, 'n');
    }
    return 0;
}

3.一些编辑很久的错误式子，pi用没有?，下次我就要用这个出题 /wx

(

)

(

)

(

)

−

(

−

)

(

)

(

−

)

(

)

(

−

⋅

−

)

(

)

(

−

)

(

)

(

−

(

−

)

(

)

⋅

(

−

)

(

)

−

(

−

)

begin{aligned}mathrm{gcd}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( (k^{2^{i}} + 1) - (k^{2^{i - 1}} + 1) Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i}} - k^{2^{i - 1}} Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1} cdot 2} - k^{2^{i - 1}} Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} times k^{2^{i - 1}} - k^{2^{i - 1}} Big) bigg) bmod p \&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} times (k^{2^{i - 1}} - 1) Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), k^{2^{l}} cdot mathrm{gcd}_{i = l + 1}^{r} Big( k^{2^{i - 1}} - 1 Big) bigg) bmod p\&= gcd bigg( (k^{2^{l}} + 1), mathrm{gcd}_{i = l}^{r - 1} Big( k^{2^{i}} - 1 Big) bigg) bmod pend{aligned}

$g c d_{i = l r} (k^{2^{i}} + 1) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l + 1 r} ((k^{2^{i}} + 1) - (k^{2^{i - 1}} + 1))) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l + 1 r} (k^{2^{i}} - k^{2^{i - 1}})) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l + 1 r} (k^{2^{i - 1} \cdot 2} - k^{2^{i - 1}})) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l + 1 r} (k^{2^{i - 1}} \times k^{2^{i - 1}} - k^{2^{i - 1}})) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l + 1 r} (k^{2^{i - 1}} \times (k^{2^{i - 1}} - 1))) m o d p = g c d ((k^{2^{l}} + 1), k^{2^{l}} \cdot g c d_{i = l + 1 r} (k^{2^{i - 1}} - 1)) m o d p = g c d ((k^{2^{l}} + 1), g c d_{i = l r - 1} (k^{2^{i}} - 1)) m o d p$

(

−

)

(

−

(

−

)

(

−

⋅

−

(

−

)

(

−

)

begin{aligned}mathrm{gcd}_{i = l}^{r} Big( k^{2^{i}} - 1 Big)&= gcd Big( k^{2^{l}} - 1, mathrm{gcd}_{i = l + 1}^{r} (k^{2^{i}} - k^{2^{i - 1}}) Big) bmod p\&= gcd Big( k^{2^{l}} - 1, k^{2^{l}} cdot mathrm{gcd}_{i = l}^{r - 1} (k^{2^{i}} - 1) Big) bmod p\&= (k^{2^{l}} - 1) bmod pend{aligned}

$g c d_{i = l r} (k^{2^{i}} - 1) = g c d (k^{2^{l}} - 1, g c d_{i = l + 1 r} (k^{2^{i}} - k^{2^{i - 1}})) m o d p = g c d (k^{2^{l}} - 1, k^{2^{l}} \cdot g c d_{i = l r - 1} (k^{2^{i}} - 1)) m o d p = (k^{2^{l}} - 1) m o d p$

所以原式可以化为

(

)

(

)

(

−

)

begin{aligned}mathrm{gcd}_{i = l}^{r} (k^{2^{i}} + 1) bmod p &= gcd ((k^{2^{l}} + 1), (k^{2^{l}} - 1)) bmod pend{aligned}

$g c d_{i = l r} (k^{2^{i}} + 1) m o d p = g c d ((k^{2^{l}} + 1), (k^{2^{l}} - 1)) m o d p$

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。

THE END

几何学线性代数

二维码

【中值滤波和最邻近插值(matlab)】

< <上一篇

因无报酬，开发者破坏 GitHub 知名开源库；AngularJS 结束生命周期；Linux 5.16 发布｜开源日报

下一篇>>

搜索内容

Visit of the Great

1.前言

2.题解

3.一些编辑很久的错误式子，pi用没有?，下次我就要用这个出题 /wx

最新文章

分类

标签云