Codeforce-CodeCraft-20 (Div. 2)-C. Primitive Primes（本原多项式+数学推导）
It is Professor R’s last class of his teaching career. Every time Professor R taught a class, he gave a special problem for the students to solve. You being his favourite student, put your heart into solving it one last time.
You are given two polynomials f(x)=a0+a1x+⋯+an−1xn−1 and g(x)=b0+b1x+⋯+bm−1xm−1, with positive integral coefficients. It is guaranteed that the cumulative GCD of the coefficients is equal to 1 for both the given polynomials. In other words, gcd(a0,a1,…,an−1)=gcd(b0,b1,…,bm−1)=1. Let h(x)=f(x)⋅g(x). Suppose that h(x)=c0+c1x+⋯+cn+m−2xn+m−2.
You are also given a prime number p. Professor R challenges you to find any t such that ct isn’t divisible by p. He guarantees you that under these conditions such t always exists. If there are several such t, output any of them.
As the input is quite large, please use fast input reading methods.
Input
The first line of the input contains three integers, n, m and p (1≤n,m≤106,2≤p≤109), — n and m are the number of terms in f(x) and g(x) respectively (one more than the degrees of the respective polynomials) and p is the given prime number.
It is guaranteed that p is prime.
The second line contains n integers a0,a1,…,an−1 (1≤ai≤109) — ai is the coefficient of xi in f(x).
The third line contains m integers b0,b1,…,bm−1 (1≤bi≤109) — bi is the coefficient of xi in g(x).
Output
Print a single integer t (0≤t≤n+m−2) — the appropriate power of x in h(x) whose coefficient isn’t divisible by the given prime p. If there are multiple powers of x that satisfy the condition, print any.
Examples
inputCopy
3 2 2
1 1 2
2 1
outputCopy
1
inputCopy
2 2 999999937
2 1
3 1
outputCopy
2
Note
In the first test case, f(x) is 2x2+x+1 and g(x) is x+2, their product h(x) being 2x3+5x2+3x+2, so the answer can be 1 or 2 as both 3 and 5 aren’t divisible by 2.
In the second test case, f(x) is x+2 and g(x) is x+3, their product h(x) being x2+5x+6, so the answer can be any of the powers as no coefficient is divisible by the given prime.
题意：
给定两个多项式长度 n 和 m ，再给定每一项的系数，由常数项到最高次项排序，其中每个多项式的系数的GCD=1。
然后再给定一个质数 p
问两个多项式相乘后得到的第三个多项式中，哪一项的系数不是 p 的倍数，输出这个项的x的幂次（下标）
如果am∗bn Mod p!=0a_m*b_n\ Mod\ p!=0am∗bn Mod p!=0，那么有am Mod p!=0a_m \ Mod \ p!=0am Mod p!=0且bn Mod p!=0b_n \ Mod \ p!=0bn Mod p!=0，因为幂是低次幂向高次幂排列，乘积也是如此，因此我们只要找到最小非0次幂不能整除P，即可。即找到最小的m和n即可。
第am项∗第bn项=am∗xm∗bn∗xn第a_m项*第b_n项=a_m*x^m*b_n*x^n第am项∗第bn项=am∗xm∗bn∗xn是第n+m项
可行性：本原多项式
如果还有问题的话，欢迎DL补充，小弟不胜感激，洗耳恭听。
#include <bits/stdc++.h>
using namespace std;
template <typename t>
void read(t &x)
{
char ch = getchar();
x = 0;
t f = 1;
while (ch < '0' || ch > '9')
f = (ch == '-' ? -1 : f), ch = getchar();
while (ch >= '0' && ch <= '9')
x = x * 10 + ch - '0', ch = getchar();
x *= f;
}
#define wi(n) printf("%d ", n)
#define wl(n) printf("%lld ", n)
#define rep(m, n, i) for (int i = m; i < n; ++i)
#define rrep(m, n, i) for (int i = m; i > n; --i)
#define P puts(" ")
typedef long long ll;
#define MOD 1000000007
#define mp(a, b) make_pair(a, b)
#define N 200005
#define fil(a, n) rep(0, n, i) read(a[i])
//---------------https://lunatic.blog.csdn.net/-------------------//
int main()
{
int m, n, p, tem;
read(n), read(m), read(p);
ll ans1 = 0, ans2 = 0;
for (int i = 0; i < n; i++)
{
read(tem);
tem %= p;
if (tem && !ans1)
ans1 = i;
}
for (int i = 0; i < m; i++)
{
read(tem);
tem %= p;
if (tem && !ans2)
ans2 = i;
}
cout << ans1 +ans2 << endl;
}
写在最后:
我叫风骨散人，名字的意思是我多想可以不低头的自由生活，可现实却不是这样。家境贫寒，总得向这个世界低头，所以我一直在奋斗，想改变我的命运给亲人好的生活，希望同样被生活绑架的你可以通过自己的努力改变现状，深知成年人的世界里没有容易二字。目前是一名在校大学生，预计考研，热爱编程，热爱技术，喜欢分享，知识无界，希望我的分享可以帮到你！
如果有什么想看的，可以私信我，如果在能力范围内，我会发布相应的博文！
感谢大家的阅读！最新文章
- MFC的定时器OnTimer
- Java之流程控制语句
- phpmyadmin Wrong permissions on configuration file, should not be world writable!
- 基于ASP.NET MVC的热插拔模块式开发框架(OrchardNoCMS)--模块开发
- 【SQL Server】SQL Server基础之存储过程
- HTML 编辑器
- ios的runtime为什么可以动态添加方法
- dell ipmi sol
- DataGridView 中CheckBox 获取状态
- STL之map、multimap
- UVAlive3713 Astronauts（2-SAT）
- 移动端开发（一. Viewport(视窗)）
- weex官方demo weex-hackernews代码解读(下）
- ASP.NET Core 源码学习之 Options[3]:IOptionsSnapshot
- vue.js移动端app实战2：首页
- CTF---Web入门第十题 Once More
- leetcode 561.Array Partition I-easy
- 在Eclipse中Tomcat配置图片保存路径
- formbuild拖拽表单设计器
- SSM框架中spring的XML文件配置
热门文章