/ ALGORITHM

玲珑杯 Round #17 problem B

Problem Information

source: It’s from the Round #17 of “LingLong” cup

Description

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

As we all know that Mr.zhu is a chef, and he has a unique salted fish making skills.
Mr.Tang is a salted fish supplier, he tells Mr.zhu that there are $N$ salted fishes (labeled from $1$ to $N$ ) which can be used to make it.
Each salted fish has a salted value $K_i $, and all $K_i $ are 0 at the beginning.
Mr.Zhu is a special person, he has a number of salons (salted fish value), for each salon $x$, he will let the salted value of all the salted fish whose label is the multiple of the $x$ xor by $1$.
Mr.Zhu now wants to know the final number of salted fish whose salted fish is $1$ after the $M$ salons of screening?

Input

输入的第一行包含一个整数 $ T(1≤T≤1000) $, 表示有 $ T $组数据。
对于每组数据:
输入第一行只有两个整数$ N(1≤N≤10^9),M(1≤M≤15) $.
接下来一行有 $ M $个整数,依次对应zhu的每个咸数 $ x(1≤x≤2*10^5) $.

The first line of the input contains an integer $T (1≤T≤1000) $ indicating that there is $T $ group data.
For each set of data:
The first line of the input contains only two integers $N (1≤N≤10^9), M (1≤M≤15) $.
The next line has $M$ integers, followed by Mr.zhu’s every salon $x (1≤x≤2 * 10 ^ 5) $.

Output

对于每组数据,输出答案.

For each set of data, output the answer.

Sample Input

2
10 1
3
10 1
1

Sample Output

3
10

Solution

我们把需要异或的数定义为被标记的数,异或值为$1$则相应于被标记的次数为奇数。
对于某一个咸数 $x$,它会标记所有标号是它倍数的咸鱼,总数加上 $1 \times \frac{N}{x}$ ;
对于任意$2$个咸数 $x,y$的 $LCM_{x,y}$, 标号是它的倍数的咸鱼在计算一个咸数的时候已经被标记了$2$次,则总数减去$ 2\times \frac{N}{LCM_{x,y}} $;
对于任意$3$个咸数 $ x, y, z $的$ LCM_{x,y,z} $, 标号是它的倍数的咸鱼在计算一个咸数时被标记了$3$次,在计算$2$个咸数的时候被减去了$6$次,但它最后需要统计为$1$次,即$ (3-6+t)=1, t=4 $, 则总数需要加上$ 4\times \frac{N}{LCM_{x,y,z}} $。
依次类推,我们发现咸数集合大小为偶数时减,为奇数时加,每次计算的系数为 $ 2^{咸数集合大小-1} $,最后统计的结果就是标记次数为奇数的咸鱼数量。

We define the number needed to XOR as the marked number, and the final XOR value is $1$ which corresponds to that the total marked times is odd.
For a certain salon $x $, it will mark all the salted fishes whose label is $x $’s multiple, so we plus the answer by $1 \times \frac{N}{x} $;
For the LCM of any two salons $ x,y $, the salted fishes whose label is $LCM_{x,y} $’s multiple have been marked twice in the calculation of one salon, then the answer need to minus $2 \times \frac{N}{LCM_{x,y}} $;
For the LCM of any three salons $x, y, z $, the salted fishes whose label is $LCM_{x,y,z} $’s multiple have been marked $3$ times in the calculation of one salon, and are subtracted $6$ times when calculating two salons, then $(3-6 + t) = 1, t = 4 $. so the answer need to add $4 \times \frac{N}{LCM_{x,y,z}} $.
And so on, we find that it needs reduction when the size of the salons is even and needs addition when the size of the salons is odd, each calculated coefficient is $2 ^ {the\ size\ of\ salons -1} $, and the final result is the size of the salt fishes whose marked times are odd.

AC code

int T;
int N, M;
int A[20];
LL ans;
LL lcm(LL a, LL b)
{
    LL x = __gcd(a,b);
    return a/x*b;
}
void LCM(int loc, int dep, LL last)
{
    if(dep&1) ans += (1<<(dep-1))*(N/last);
    else ans -= (1<<(dep-1))*(N/last);
    for(int i=loc+1;i<=M;i++)
    {
        LCM(i, dep+1, lcm(last, A[i]));
    }
}

void solve()
{
    ans = 0;
    for(int i=1;i<=M;i++)    
    {
        LCM(i,1,A[i]);
    }
    printf("%lld\n", ans);
}

int main()
{
    //std::ios::sync_with_stdio(false);
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d", &N, &M);
        for(int i=1;i<=M;i++) scanf("%d", &A[i]);
        solve();
    }
    //system("pause"A);
}