UVA 10951 - Polynomial GCD(数论)

UVA 10951 - Polynomial GCD

题目链接

题意:给定两个多项式,求多项式的gcd,要求首项次数为1,多项式中的运算都%n,并且n为素数.

思路:和gcd基本一样,只不过传入的是两个多项式,由于有%n这个条件,所以计算过程可以用乘法逆去计算除法模,然后最后输出的时候每项除掉首项的次数就是答案了.

代码:

#include #include #include using namespace std; int n; vector f, g; int exgcd(int a, int b, int &x, int &y) { if (!b) {x = 1; y = 0; return a;} int d = exgcd(b, a % b, y, x); y -= a / b * x; return d; } int inv(int a, int n) { int x, y; exgcd(a, n, x , y); return (x + n) % n; } vector pmod(vector f, vector g) { int fz = f.size(), gz = g.size(); for (int i = 0; i ans; int p = -1; for (int i = 0; i = 0) for (int i = p; i gcd(vector f, vector g) { if (g.size() == 0) return f; return gcd(g, pmod(f, g)); } int main() { int cas = 0; while (~scanf("%d", &n) && n) { f.clear(); g.clear(); int a, k; scanf("%d", &a); for (int i = 0; i ans = gcd(f, g); int tmp = inv(ans[0], n), ansz = ans.size();; printf("Case %d: %d", ++cas, ansz - 1); for (int i = 0; i

点击复制链接 与好友分享!回本站首页
您对本文章有什么意见或着疑问吗?请到论坛讨论您的关注和建议是我们前行的参考和动力
上一篇:CodeForces 19B Checkout Assistant dp
下一篇:HDU 1317 XYZZY
相关文章

hdu 3826 数论 n能否被含有因子是一

数论中的基本算法 POJ 1845 SPOJ

hdu 1695 综合数论 欧拉函数 分

hdu 1576(数论之扩展欧几里得)

HDU 3547 DIY Cube 数论- Polya定理

poj3358数论(欧拉定理)

(数论2.1.3)UVA 10533 Digit Primes

(Relax 数论1.7)POJ 2407 Relative

(Relax 数论1.8)POJ 2478 Farey S

(Relax 数论1.11)POJ 1595 Prime

图文推荐
UVA 10951 - Polynomial GCD(数论)
ZOJ 3640 Help Me
UVA 10951 - Polynomial GCD(数论)
CF 518C(Anya and
UVA 10951 - Polynomial GCD(数论)
hdu 1016 Prime R
UVA - 11987 - A

分类:默认分类 时间:2012-01-04 人气:15
本文关键词:
分享到:

相关文章

  • UVA - 12075 Counting Triangles 2012-09-02

    Description Triangles are polygons with three sides and strictly positive area. Lattice triangles are the triangles all whose vertexes have integer coordinates. In this problem you have to find the number of lattice triangles in anMxN grid. For examp

  • UVa 11426 GCD - Extreme (II) / 素数筛选 + 欧拉函数 2014-05-01

    输入正整数n,求gcd(1,2)+gcd(1,3)+gcd(2,3)+...+gcd(n-1,n) 设f(n) = gcd(1,n)+gcd(2,n)+...+gcd(n-1,n) 所求s(n) = f(2)+f(3)+...+f(n) = s(n-1)+f(n); gcd(x,n) = i gcd(x/i,n/i) = 1 满足条件的x/i有phi(n/i)个(欧拉函数) 可以按照素数筛选发那样做枚举因子i 然后f[n] += i*phi[n/i]; phi_table 用到了素数筛选发求出从

  • HDU1695 GCD 数论之 莫比乌斯反演 2012-03-13

    做了一段时间的DP,继续回头啃数论了,这是一道莫比乌斯反演的题目,比较繁琐 给你a,b,c,d,k五个数,其中a=c=1固定的,让你从[a,b]中找出x,[c,d]中找出y,是的gcd(x,y) == k,注意gcd(x,y) 与gcd(y,x)归为同一种,问一共能找到多少组x,y; 分析: 因为gcd(x,y) = k,充要条件gcd(x/k,y/k) = 1,所以区间可以缩小为[1/k,b/k],[1/k,d/k],注意此处的d是题目中的d,不是数论中默认的d最大为公约数含义,这样酒吧问题转

  • HDOJ 5019 Revenge of GCD 2012-04-03

    第k大GCD = GCD/第K大因子 Revenge of GCD Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 877 Accepted Submission(s): 259 Problem Description In mathematics, the greatest common divisor (gcd), also known

  • uva - UVA 1388 - Graveyard (数学推理) 2012-04-09

    题意:有一个周长为10000的圆上等距分布着n个雕塑,现在又加入m个雕塑,位置随意,希望n+m个雕塑仍然均匀分布。这就要移动其中一些雕像,求移动的最小距离。 方法:仍然是刘大大的例题,假定某一个雕像不动,作为坐标原点,其他雕像按照逆时针标上到原点的距离标号。不是真是距离而是按比例缩小后的。接下来移动到离它最近的位置,例题用了四舍五入,感觉是不对的,例如x = 0.5, y = 1.499999,但是x和y的差还是小于1,而相邻雕像的距离才为1,所以这样看也是可行的。 注意:floor和四舍五入的

  • uva 1069 - Always an integer(数学+暴力) 2012-06-26

    题目链接:uva 1069 - Always an integer 题目大意:给出一个多次多项式,问说是否对于任意正整数n来说结构均为整数。 解题思路:首先处理出字符串,然后枚举n从1到k+1判断即可,k为多项式中出现过的最大幂数指。 P为多项式,d为除数,k为多项式中最大的次数 当k=0时,P中不存在n变量,所以直接计算判断即可 当k=1时,P是一次多项式,那么P(n+1)?P(n)=a,a为常数,也就是说P(i)为等差数列,如果首项P(1)和公差P(2)-P(1)为d的倍数即可,等价与判断P

  • UVA - 1069 Always an integer (模拟) 2012-07-01

    Description Combinatorics is a branch of mathematics chiefly concerned with counting discrete objects. For instance, how many ways can you pick two people out of a crowd ofn people? Into how many regions can you divide a circular disk by connectingn

  • HDU 1722 Cake (GCD) 2012-07-11

    Cake Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others) Total Submission(s): 2609 Accepted Submission(s): 1253 Problem Description 一次生日Party可能有p人或者q人参加,现准备有一个大蛋糕.问最少要将蛋糕切成多少块(每块大小不一定相等),才能使p人或者q人出席的任何一种情况,都能平均将蛋糕分食. Inpu

  • Uva 106-Fermat vs. Pythagoras(勾股数性质) 2012-07-20

    题目链接:点击打开链接 题意:给出N,x^2+y^2=z^2 小于等于N的解(互素)的个数以及小于N的个数除掉所有解(包括不互素)已经用掉的数。 度娘给出勾股数的定义:只考虑互素的解,给出勾股数公式 a=2*m*n ,b=m*m-n*n ,c=m*m+n*n; 枚举m,n ,复杂度 O(log(N)^2) #include #include #include #include #include #include #include #include #include #include #inclu

Copyright (C) quwantang.com, All Rights Reserved.

趣玩堂 版权所有 京ICP备15002868号

processed in 0.033 (s). 10 q(s)