【题解】SCOI2010幸运数字
2024-09-02 23:07:21
最近在学习容斥相关,于是就看到了这个题。一开始以为是补集转化,但是观察一下马上发现不可行,好像直接做会比较容易一些。一个数满足要求的充要条件即为是一个幸运数字的倍数,那么容斥可以轻松搞定,只要枚举是一个数字/两个数字/三个数字的倍数……即可。打一个表找出<1e10的所有幸运数……竟然有2043个。不过显然其中互为倍数的那些个我们可以直接删掉其中大一些的那个数。这样删去之后,还剩下943个数。
到这里我突然觉得好懵逼啊……左想右想再也想不出新的优化。于是看题解,发现竟然真的是爆搜加了两个剪枝。其中一个是当LCM>B的时候直接返回(不会产生贡献),第二个是从大到小排序,让大的数更容易被淘汰掉。果然爆搜的复杂度是非常玄妙的一件事……竟然跑得飞快?启发是一定要勇敢的打暴力,没准就过了(・ω <)
不过为什么只有我一个要开unsigned long long 捏……
#include <bits/stdc++.h>
using namespace std;
#define int unsigned long long
#define ll long long
#define maxn 5000
int A, B, ans, luck[maxn], data[maxn];
int tot, cnt; int read()
{
int x = , k = ;
char c;
c = getchar();
while(c < '' || c > '') { if(c == '-') k = -; c = getchar(); }
while(c >= '' && c <= '') x = x * + c - '', c = getchar();
return x * k;
} void dfs(int now, int n)
{
if(now) luck[++ cnt] = now;
if(now * (ll) + (ll) <= n) dfs(now * (ll) + (ll) , n);
if(now * (ll) + (ll) <= n) dfs(now * (ll) + (ll) , n);
} bool cmp(int a, int b) { return a > b; } int GCD(int a, int b)
{
while(b)
{
int c = a % b;
a = b;
b = c;
}
return a;
} void solve(int num, int cnt, int lcm)
{
if(num > tot)
{
if(cnt)
{
if(cnt & ) ans += (B / lcm) - ((A - ) / lcm);
else ans -= (B / lcm) - ((A - ) / lcm);
}
return;
}
solve(num + , cnt, lcm);
int gcd = GCD(data[num], lcm);
int LCM = (lcm / gcd) * data[num];
if(LCM <= B) solve(num + , cnt + , LCM);
} signed main()
{
A = read(), B = read();
dfs(, B);
sort(luck + , luck + + cnt);
for(int i = ; i <= cnt; i ++)
{
data[++ tot] = luck[i];
for(int j = ; j < tot; j ++)
if(!(luck[i] % data[j])) { tot --; break; }
}
sort(data + , data + + tot, cmp);
solve(, , );
printf("%lld\n", ans);
return ;
}
最新文章
- java spring mvc完整包下载地址
- Python 循环判断和数据类型
- sd_cms置顶新闻,背景颜色突击显示
- 浅析.NET泛型
- ArcMap中的名称冲突问题
- HDU 1031 Design T-Shirt
- Android自定义控件(二)——有弹性的ScrollView
- 单片微机原理P3:80C51外部拓展系统
- Redis intset
- SQL Server编程系列(1):SMO介绍
- Wechat 微信端调用“微信支付接口”的正确方式
- (八十一)利用系统自带App来实现导航
- Android中的Message机制
- golang 如何将imagemagick 和golang 打包到docker 环境中
- map集合实现缓存
- 用C# BigInteger实现的BigDecimal类,终于可以直接做四则运算了。
- PC端的鼠标拖拽滑动
- 操作系统04_IO管理
- pThreads线程(二) 线程同步--互斥量/锁
- Sphinx/Coreseek 4.1 执行 buildconf.sh 报错,无法生成configure文件