Codeforces Round #460 (Div. 2) E. Congruence Equation 数学

2023-10-20 17:59

本文主要是介绍Codeforces Round #460 (Div. 2) E. Congruence Equation 数学,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

E. Congruence Equation

在这里插入图片描述

solution

{ i ∗ a i % p = b , i < p − 1 , ( t − k ) ∗ a t % p = b , i ≥ p − 1 , i = ( p − 1 ) k + t . \begin{cases} i*a^i\%p=b,i<p-1, \\(t-k)*a^{t}\%p=b,i≥p-1,i=(p-1)k+t. \end{cases} {iai%p=bi<p1,(tk)at%p=bip1i=(p1)k+t.

分别枚举 i , t . i,t. it.

code

/*SiberianSquirrel*/
/*CuteKiloFish*/
#include<bits/stdc++.h>using namespace std;
typedef long long ll;const double PI = acos(-1), eps = 1e-8;
/*const int MOD = 998244353, r = 119, k = 23, g = 3;
const int MOD = 1004535809, r = 479, k = 21, g = 3;*/
const int INF = 0x3f3f3f3f, MOD = 1e9 + 7;
const int M = 1e7 + 10, N= 2e6 + 10;int sgn(double x) {if(fabs(x) < eps) return 0;return x < 0? -1: 1;
}
//inline int rnd(){static int seed=2333;return seed=(((seed*666666ll+20050818)%998244353)^1000000007)%1004535809;}
//double Rand() {return (double)rand() / RAND_MAX;}ll a, b, p, x;
int inv[N];void solve(ll res = 0) {ll temp = a;for(int i = 1; i < min(p - 1, x + 1); ++ i) {if(1ll * i * temp % p == b) res ++;temp = temp * a % p;}temp = 1;for(int i = 0; i <= p - 2; ++ i) {ll t = ((b * inv[temp] - i + p) % p) * inv[p-1] % p;res += ((x - i) / (p - 1) - t) / p;if((t && t * (p - 1) + i <= x)) res ++;temp = temp * a % p;}cout << res << endl;
}int main() {ios::sync_with_stdio(false);cin.tie(0);cout.tie(nullptr);
// srand(time(0));
#ifdef ACM_LOCALfreopen("input", "r", stdin);freopen("output", "w", stdout);
#endifint o = 1;
//	cin >> o;while(o --) {cin >> a >> b >> p >> x;inv[1] = 1;for(int i = 2; i < N; ++ i)inv[i] = 1ll * (p - p / i) * inv[p % i] % p;solve();}return 0;
}

这篇关于Codeforces Round #460 (Div. 2) E. Congruence Equation 数学的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/248745

相关文章

使用C#代码计算数学表达式实例

《使用C#代码计算数学表达式实例》这段文字主要讲述了如何使用C#语言来计算数学表达式,该程序通过使用Dictionary保存变量,定义了运算符优先级,并实现了EvaluateExpression方法来... 目录C#代码计算数学表达式该方法很长,因此我将分段描述下面的代码片段显示了下一步以下代码显示该方法如

uva 10014 Simple calculations(数学推导)

直接按照题意来推导最后的结果就行了。 开始的时候只做到了第一个推导,第二次没有继续下去。 代码: #include<stdio.h>int main(){int T, n, i;double a, aa, sum, temp, ans;scanf("%d", &T);while(T--){scanf("%d", &n);scanf("%lf", &first);scanf

uva 10025 The ? 1 ? 2 ? ... ? n = k problem(数学)

题意是    ?  1  ?  2  ?  ...  ?  n = k 式子中给k,? 处可以填 + 也可以填 - ,问最小满足条件的n。 e.g k = 12  - 1 + 2 + 3 + 4 + 5 + 6 - 7 = 12 with n = 7。 先给证明,令 S(n) = 1 + 2 + 3 + 4 + 5 + .... + n 暴搜n,搜出当 S(n) >=

uva 11044 Searching for Nessy(小学数学)

题意是给出一个n*m的格子,求出里面有多少个不重合的九宫格。 (rows / 3) * (columns / 3) K.o 代码: #include <stdio.h>int main(){int ncase;scanf("%d", &ncase);while (ncase--){int rows, columns;scanf("%d%d", &rows, &col

【生成模型系列(初级)】嵌入(Embedding)方程——自然语言处理的数学灵魂【通俗理解】

【通俗理解】嵌入(Embedding)方程——自然语言处理的数学灵魂 关键词提炼 #嵌入方程 #自然语言处理 #词向量 #机器学习 #神经网络 #向量空间模型 #Siri #Google翻译 #AlexNet 第一节:嵌入方程的类比与核心概念【尽可能通俗】 嵌入方程可以被看作是自然语言处理中的“翻译机”,它将文本中的单词或短语转换成计算机能够理解的数学形式,即向量。 正如翻译机将一种语言

Codeforces Round #240 (Div. 2) E分治算法探究1

Codeforces Round #240 (Div. 2) E  http://codeforces.com/contest/415/problem/E 2^n个数,每次操作将其分成2^q份,对于每一份内部的数进行翻转(逆序),每次操作完后输出操作后新序列的逆序对数。 图一:  划分子问题。 图二: 分而治之,=>  合并 。 图三: 回溯:

Codeforces Round #261 (Div. 2)小记

A  XX注意最后输出满足条件,我也不知道为什么写的这么长。 #define X first#define Y secondvector<pair<int , int> > a ;int can(pair<int , int> c){return -1000 <= c.X && c.X <= 1000&& -1000 <= c.Y && c.Y <= 1000 ;}int m

Codeforces Beta Round #47 C凸包 (最终写法)

题意慢慢看。 typedef long long LL ;int cmp(double x){if(fabs(x) < 1e-8) return 0 ;return x > 0 ? 1 : -1 ;}struct point{double x , y ;point(){}point(double _x , double _y):x(_x) , y(_y){}point op

Codeforces Round #113 (Div. 2) B 判断多边形是否在凸包内

题目点击打开链接 凸多边形A, 多边形B, 判断B是否严格在A内。  注意AB有重点 。  将A,B上的点合在一起求凸包,如果凸包上的点是B的某个点,则B肯定不在A内。 或者说B上的某点在凸包的边上则也说明B不严格在A里面。 这个处理有个巧妙的方法,只需在求凸包的时候, <=  改成< 也就是说凸包一条边上的所有点都重复点都记录在凸包里面了。 另外不能去重点。 int

Codeforces 482B 线段树

求是否存在这样的n个数; m次操作,每次操作就是三个数 l ,r,val          a[l] & a[l+1] &......&a[r] = val 就是区间l---r上的与的值为val 。 也就是意味着区间[L , R] 每个数要执行 | val 操作  最后判断  a[l] & a[l+1] &......&a[r] 是否= val import ja