首页 > 代码库 > “玲珑杯”线上赛 Round #17 河南专场 B.震惊，99%+的中国人都会算错的问题

“玲珑杯”线上赛 Round #17 河南专场 B.震惊，99%+的中国人都会算错的问题

2024-10-19 02:21:39   212人阅读

1138 - 震惊，99%+的中国人都会算错的问题

Time Limit：4s Memory Limit：128MByte

Submissions：304Solved：84

DESCRIPTION

众所周知zhu是一个大厨，zhu一直有自己独特的咸鱼制作技巧.
tang是一个咸鱼供应商，他告诉zhu在他那里面有NN条咸鱼（标号从1到N）可以被用来制作.
每条咸鱼都有一个咸鱼值KiKi，初始时所有KiKi都是00.
zhu是一个特别的人，他有MM个咸数（咸鱼数字）, 对于每个咸数xx，他都会让所有满足标号是xx倍数的咸鱼的咸鱼值异或上11.
zhu现在想知道经过了这MM个咸数的筛选之后，最终有多少条的咸鱼的咸鱼值是11?

INPUT
输入的第一行包含一个整数T(1≤T≤1000)T(1≤T≤1000)，表示有TT组数据. 对于每组数据： 输入第一行只有两个整数N(1≤N≤109)N(1≤N≤109),M(1≤M≤15)M(1≤M≤15). 接下来一行有MM个整数，依次对应zhu的每个咸数(1≤咸数≤2?1051≤咸数≤2?105).
OUTPUT
对于每组数据，输出答案.
SAMPLE INPUT
2 10 1 3 10 1 1
SAMPLE OUTPUT
3 10
 
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<string>
#include<algorithm>
#include<iostream>
#include<queue>
#include<map>
#include<cmath>
#include<set>
#include<stack>
#define ll long long
#define pb push_back
#define max(x,y) ((x)>(y)?(x):(y))
#define min(x,y) ((x)>(y)?(y):(x))
#define cls(name,x) memset(name,x,sizeof(name))
using namespace std;
const int inf=1e9+10;
const ll llinf=1e16+10;
const int maxn=1e5+10;
const int maxm=1e2+10;
const int mod=1e9+7;
ll n;
int m;
ll num[maxm];
ll gcd(ll a,ll b)
{
    if(b==0) return a;
    else return gcd(b,a%b);
}
ll ans;
void dfs(ll k,int pos,int c)
{
    if(pos==m+1)
    {
        if(c%2==1) ans+=n/k*(1<<(c-1));
        else ans-=n/k*(1<<(c-1));
        return ;
    }
    if(k<=n)
    {
        dfs(k,pos+1,c);
        k=k*num[pos]/gcd(k,num[pos]);
        dfs(k,pos+1,c+1);
    }
}
int main()
{
    //freopen("in.txt","r",stdin);
    int ncas;
    scanf("%d",&ncas);
    while(ncas--)
    {
        ans=0;
        scanf("%lld %d",&n,&m);
        for(int i=1;i<=m;i++)
            scanf("%lld",&num[i]);
        for(int i=1;i<=m;i++)
            dfs(num[i],i+1,1);
        printf("%lld\n",ans);
    }
    return 0;
}

 

“玲珑杯”线上赛 Round #17 河南专场 B.震惊，99%+的中国人都会算错的问题


联系
我们