Codeforces 900D-Unusual Sequences

53 阅读 0 评论 35 点赞

我是靠谱客的博主火星上哈密瓜，最近开发中收集的这篇文章主要介绍Codeforces 900D-Unusual Sequences，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

Count the number of distinct sequences a1, a2, ..., an (1 ≤ ai) consisting of positive integers such that gcd(a1, a2, ..., an) = x and $\text{[math]}$ . As this number could be large, print the answer modulo 109 + 7.

gcd here means the greatest common divisor.

Input

The only line contains two positive integers x and y (1 ≤ x, y ≤ 109).

Output

Print the number of such sequences modulo 109 + 7.

   Examples 
 
     input 
   
3 9

     output 
   
3

     input 
   
5 8

     output 
   
0

Note

There are three suitable sequences in the first test: (3, 3, 3), (3, 6), (6, 3).

There are no suitable sequences in the second test.

题意：问能构造出多少个序列满足，序列中所有元素的gcd为x，序列中所有元素的和为y

解题思路：容斥，分别求出gcd为x，2*x……的数量，然后减去多余即可

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <cmath>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
#include <bitset>
#include <functional>
#include <ctime>

using namespace std;

#define LL long long
const int INF = 0x3f3f3f3f;
const LL mod = 1e9 + 7;
map<int, LL>mp;

LL qpow(int k)
{
	LL ans = 1, x = 2;
	while (k)
	{
		if (k & 1) (ans *= x) %= mod;
		(x *= x) %= mod;
		k >>= 1;
	}
	return ans;
}

LL solve(int x)
{
	if (x == 1) return 1;
	if (mp[x]) return mp[x];
	mp[x] = qpow(x - 1);//隔板法可以计算出把一个数x分解成可以由几个数组成的序列有2^(x−1)个
	for (int i = 2; i*i <= x; i++)
	{
		if (x%i == 0)
		{
			mp[x] = (mp[x] - solve(x / i) + mod) % mod;
			if (i != x / i) mp[x] = (mp[x] - solve(i) + mod) % mod;
		}
	}
	mp[x] = (mp[x] - solve(1) + mod) % mod;
	return mp[x];
}

int main()
{
	int x, y;
	while (~scanf("%d%d", &x, &y))
	{
		if (y%x != 0) { printf("0n"); continue; }
		mp.clear();
		printf("%lldn", solve(y / x));
	}
	return 0;
}