Submission #21418

#	Time	Username	Problem	Language	Result	Execution time	Memory
21418		gs14004	Actual visible points (kriii2_AC)	C++11	4 / 4	86 ms	6708 KiB

AC

#include <bits/stdc++.h>
using namespace std;
typedef long long lint;
typedef pair<int, int> pi;
const int mod = 1e9 + 7;

lint ipow(lint x, lint p){
	lint ret = 1, piv = x % mod;
	while(p){
		if(p&1) ret *= piv;
		piv *= piv;
		ret %= mod;
		piv %= mod;
		p >>= 1;
	}
	return ret % mod;
}

lint fact[200005], invf[200005];

lint bino(int x, int y){
	return fact[x] * (invf[x-y] * invf[y] % mod) % mod;
}

int n, q, chk[100005];
lint dp[100005];
int mob[100005];

int main(){
	fact[0] = invf[0] = 1;
	for(int i=1; i<=200000; i++){
		fact[i] = fact[i-1] * i % mod;
		invf[i] = ipow(fact[i], mod-2);
	}
	cin >> n >> q;
	for(int i=0; i<q; i++){
		int x;
		scanf("%d",&x);
		chk[x] = 1;
	}
	for(int i=1; i<=100000; i++){
		dp[i] += bino(n + i - 2, n - 1);
		dp[i] %= mod;
		for(int j=2*i; j<=100000; j+=i){
			dp[j] += mod - dp[i];
		}
	}
	lint ret = 0;
	for(int i=1; i<=100000; i++){
		for(int j=i; j<=100000; j+=i){
			if(chk[j]){
				chk[i] = 1;
				break;
			}
		}
		if(chk[i]) ret += dp[i];
	}
	ret %= mod;
	cout << ret << endl;
}

Compilation message (stderr)

AC.cpp: In function 'int main()':
AC.cpp:38:17: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&x);
                 ^

• Subtask 1: 1 / 1
• Subtask 2: 3 / 3