CF687B Remainders Game

题意:已知n个数,第i个为ci,给定一个数x mod ci的结果,再给点一个k,问能不能知道x mod k的值?

分析:刚看题目的我一脸蒙蔽,对题意有点不理解,能的情况似乎有很多,我该从哪里下手呢?

先从不能的情况来看,可以知道,如果不能知道x mod k的值,当且仅当有两个解x1,x2, x1 ≡ x2(mod ci)x1 ≡? x2 (mod k) 左边这个是不同余的意思,

为什么是这样的呢?因为题目中说x mod k的值是唯一的,我们却会出现两个满足题意的x值 mod k的值不同,这就矛盾了。

那么我们怎样求解这两个同余式呢?如果x1 ≡ x2(mod ci),那么(x1 - x2) % ci = 0,所以x1 - x2一定是ci的最小公倍数的倍数,

然后对第二个式子变形一下:(x1 - x2) % k != 0,也就是说k不整除lcm{ci}那么这道题就变成了要我们求解lcm{ci}到底是不是k的倍数。

但是直接求会lcm会爆掉啊,如果取模的话涉及到除法要求逆元复杂度又会爆炸,该怎么处理?

正确的方法是分解质因数:将k表示为p1^k1 * p2 ^ k2 * ... *pn ^ kn的形式,如果lcm{ci}是k的倍数,那么p1^k1、p2^k2...pn^kn一定会全部

出现在某些ci中,我们只需要在读入的时候检验一下打个标记就好了。一位大神说的对:lcm就是质因子的并集,gcd就是质因子的交集,

遇到gcd、lcm,分解一下质因子不失为一种好的方法。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<queue>
#include<cmath>

using namespace std;

int n, k, c,tot,prime[100010];
bool vis[100010];

int main()
{
    scanf("%d%d", &n, &k);
    for (int i = 2; i <= sqrt(k); i++)
    {
        if (k % i == 0)
        {
            int t = 1;
            while (k % i == 0)
            {
                t *= i;
                k /= i;
            }
            prime[++tot] = t;
        }
    }
    if (k)
        prime[++tot] = k;
    for (int i = 1; i <= n; i++)
    {
        int c;
        scanf("%d", &c);
        for (int j = 1; j <= tot; j++)
            if (c % prime[j] == 0)
                vis[j] = 1;
    }
    for (int i = 1; i <= tot; i++)
        if (!vis[i])
        {
        printf("No\n");
        return 0;
        }
    printf("Yes\n");

    return 0;
}
时间: 08-18

CF687B Remainders Game的相关文章

Codeforces Round #360 (Div. 2) D. Remainders Game(中国剩余定理)

D. Remainders Game Today Pari and Arya are playing a game called Remainders. Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value . There are n ancient numbers c1, c2, ..., cn and Pari has to tell Arya  i

codeforces 360 D - Remainders Game

D - Remainders Game Description Today Pari and Arya are playing a game called Remainders. Pari chooses two positive integer x and k, and tells Arya k but not x. Arya have to find the value . There are n ancient numbersc1,  c2, ..., cn and Pari has to

Sum of Remainders(数学题)

F - Sum of Remainders Time Limit:2000MS     Memory Limit:262144KB     64bit IO Format:%I64d & %I64u Submit Status Practice CodeForces 616E Description Calculate the value of the sum: n mod 1 + n mod 2 + n mod 3 + ... + n mod m. As the result can be v

codeforces 616E. Sum of Remainders 数学

题目链接 给两个数n, m. 求n%1+n%2+.......+n%m的值. 首先, n%i = n-n/i*i, 那么原式转化为n*m-sigma(i:1 to m)(n/i*i). 然后我们可以发现  1/4 = 2/4 = 3/4 = 0, 4/4 = 5/4 = 6/4 = 7/4 = 1. 所以可以将这些结果分成很多块, 按块算结果. 注意计算过程中时刻避免爆longlong. #include <iostream> #include <vector> #include

CodeForces 687B Remainders Game

数论. 如果$x$不唯一,假设存在两个解,较大的为${x_1}$,较小的为${x_2}$. 那么, $\left\{ {\begin{array}{*{20}{c}}{{x_1}\% {c_i} = {x_2}\% {c_i}}\\{{x_1}\% k \ne {x_2}\% k}\end{array}} \right. \Rightarrow \left\{ {\begin{array}{*{20}{c}}{({x_1} - {x_2})\% {c_i} = 0}\\{({x_1} - {x_

Codeforces 688D Remainders Game 数学

题意:Pari选了两个数x,k,已知k和n个数c[i],也能"知道"x%c[i],问是否x%k的值是否唯一?n,k,c[i]<=1e6 假如存在x1,x2满足:x1和x2同余c[i](i=1..n),但是x1%k!=x2%k 则此时不能确定x%k的值,答案为no即(x1-x2)%c[i]==0 因为lcm(c[1]..c[n])|(x1-x2) k不整除(x1-x2) k也不整除lcm(c[1]..c[n]) 该条件为必要条件.证明充分性很简单 构造x1=2*lcm,x2=lcm

Educational Codeforces Round 5 E. Sum of Remainders (思维题)

题目链接:http://codeforces.com/problemset/problem/616/E 题意很简单就不说了. 因为n % x = n - n / x * x 所以答案就等于 n * m - (n/1*1 + n/2*2 ... n/m*m) 在根号n复杂度枚举x,注意一点当m>n时,后面一段加起来就等于0,就不用再枚举了. 中间一段x1 ~ x2 的n/x可能相等,所以相等的一段等差数列求和. 1 //#pragma comment(linker, "/STACK:1024

codeforces 688D - Remainders Game 数学相关

题意:给你x%ci=bi(x未知),是否能确定x%k的值(k已知) 分析:只要保证k能整除ci的最小公倍数即可,由于太大,所以通过暴力分解因子的办法来判断 #include <cstdio> #include <iostream> #include <ctime> #include <vector> #include <cmath> #include <map> #include <set> #include <st

Codeforces 999D Equalize the Remainders 【数据结构】【贪心】

考场的时候想到的n*m做法tle了,正解是O(n+m) 首先想到一个性质是不管a[i],a[j]相差多少,只要a[i],a[j]同余,那想让他们increase后%m得到另一个余数,那他们需要increse的次数是相等的. 所以我们想到把n个数按%m从0到m-1分成m类.这样就能贪心了,因为如果%m为0这样的数大于n/m个,那这样说明这里面的v.size()-n/m个数至少要加1,我们把这些多出来的%m为0的数转化成%m为1的数:如果小于n/m先不处理.一遍扫完我们发现m-1这一项会有很多数(因