Codeforces Round #428 (Div. 2) D. Winter is here[数论 II]

2021-05-12 16:28

阅读：465

标签：数论 main eps ios fstream algo lin 二进制 air

题目：http://codeforces.com/contest/839/problem/D

技术分享

题意：找出每种情况使得所有数字gcd不为1，对答案的贡献为gcd值乘数字个数。

题解：因为数字不大，可以哈希出每种数字的个数，然后从后往前，f[i]代表在gcd==i时存在的数字搭配种数。每次计算i时，要减去计算过的种数，所以从后向前计算。每个数字贡献次数为${2}^{sum-1}$（写二进制数的情况可以观察出来），所有数字贡献为$sum*{2}^{sum-1}$ 2次x次方可以先预处理取模出来。

 1 #define _CRT_SECURE_NO_DEPRECATE
 2 #pragma comment(linker, "/STACK:102400000,102400000")
 3 #include 4 #include 5 #include 6 #include 7 #include  
 8 #include 9 #include10 #include11 #include12 #include13 #includestring>  
14 #include15 #include16 #include17 #includeset>
18 #include19 #define pii pair20 #define mod 1000000007
21 #define mp make_pair
22 #define pi acos(-1)
23 #define eps 0.00000001
24 #define mst(a,i) memset(a,i,sizeof(a))
25 #define all(n) n.begin(),n.end()
26 #define lson(x) ((x27 #define rson(x) ((x28 #define inf 0x3f3f3f3f
29 typedef long long ll;
30 typedef unsigned long long ull;
31 using namespace std;
32 const int maxn = 1e6 + 5;
33 ll savepow[maxn];
34 int cnt[maxn];
35 ll f[maxn];
36 int main()
37 {
38     ios::sync_with_stdio(false);
39     cin.tie(0); cout.tie(0);
40     int i, j, k, m, n;
41     cin >> n;
42     for (int i = 1; i i)
43     {
44         cin >> k;
45         cnt[k]++;
46     }
47     savepow[0] = 1;
48     for (int i = 1; i 1000000; ++i)savepow[i] = (savepow[i - 1] 1) % mod;
49     ll ans = 0;
50     for (ll i = 1000000; i > 1; --i)
51     {
52         int sum = 0;
53         for (int j = i; j  i)
54             sum += cnt[j];
55         if (sum)
56         {
57             ll tempans = 0;
58             tempans = 1LL * sum*savepow[sum - 1] % mod;
59             for (int j = i + i; j  i)
60                 tempans = (tempans - f[j] + mod) % mod;
61             f[i] = tempans;
62             ans = (ans + i*f[i]) % mod;
63         }
64     }
65     cout  endl;
66     return 0;
67 }

Codeforces Round #428 (Div. 2) D. Winter is here[数论 II]

标签：数论 main eps ios fstream algo lin 二进制 air

原文地址：http://www.cnblogs.com/Meternal/p/7569811.html

上一篇：C# 创建、部署、调用 webservice 的简单列子

下一篇：手动添加winform的combobox和listbox名称和值

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：Codeforces Round #428 (Div. 2) D. Winter is here[数论 II]
文章链接：http://soscw.com/index.php/essay/84764.html

亲，登录后才可以留言！

Codeforces Round #428 (Div. 2) D. Winter is here[数论 II]

评论

热门文章

推荐文章

最新文章

置顶文章