Wannafly挑战赛22---A 计算器-白红宇

Wannafly挑战赛22---A 计算器

阅读量：4217 次

发布时间：2019-05-26

本文共 993 字，大约阅读时间需要 3 分钟。

链接：

来源：牛客网

时间限制：C/C++ 1秒，其他语言2秒

空间限制：C/C++ 262144K，其他语言524288K

64bit IO Format: %lld

题目描述

有一个计数器，计数器的初始值为0，每次操作你可以把计数器的值加上a1,a2,...,an中的任意一个整数，操作次数不限（可以为0次），问计数器的值对m取模后有几种可能。

输入描述:

第一行两个整数n,m接下来一行n个整数表示a1,a2,...,an1≤n≤1001≤m,a1,a2,...,an≤1000000000

输出描述:

输出一个整数表示答案

示例1

输入

3 66 4 8

输出

思路：

记 d = gcd(a1,a2,a3..,an)

根据裴蜀定理， a1x1+a2x2 + ... + anxn = p 有解则 p = dx（x 为整数）,题意求 p%m = t （求t的可能个数）

p%m = t <==> dx - my = t <==> dx + m(-y) = t <==> gcd(d,m) | t (|表示整除) 因为 t为对m 的余数，故 t < m

所以问题转化为了求数 r = gcd(d,m) 的倍数，满足 t < m，可能为 1r,2r,3*r ....

数量即为 m/r (下取整个)。

code:

#include
   
    #include
    
     #include
     
      #include
      #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            
             using namespace std;typedef long long LL;LL gcd(LL a, LL b){ if(a < b){ int t = a; a = b; b = t; } return b == 0 ? a:gcd(b,a%b);}int main() { LL n,m; cin >> n >> m; //注意初始为m LL d = m; LL in; for(int i = 0; i < n; ++i){ cin >> in; d = gcd(d,in); } cout << LL(m/d); return 0; }