【hdu 4135】Co-prime
2024-08-31 08:13:59
【题目链接】:http://acm.hdu.edu.cn/showproblem.php?pid=4135
【题意】
让你求出[a..b]这个区间内和N互质的数的个数;
【题解】
利用前缀和,求出[1..a-1]和a[1..b]这两个区间内和N互质的数的个数;
方法是;
从小到大求出N的所有因子xi;
然后从大到小枚举每个因子xi;
可以求出[1..t]内和N的最大公因数为xi的个数设为f[xi];
(减去大于xi且为xi的倍数的y就好,即f[xi]-=f[y],一开始f[xi]=t/xi);
(因为显然f[y]是那些虽然是xi的倍数,但gcd不为xi的数)
最后也就能顺理成章的求出f[1]了
【Number Of WA】
1(没开LL,QAQ)
【完整代码】
#include <bits/stdc++.h>
using namespace std;
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define LL long long
#define rep1(i,a,b) for (int i = a;i <= b;i++)
#define rep2(i,a,b) for (int i = a;i >= b;i--)
#define mp make_pair
#define pb push_back
#define fi first
#define se second
#define ms(x,y) memset(x,y,sizeof x)
typedef pair<int,int> pii;
typedef pair<LL,LL> pll;
const int dx[9] = {0,1,-1,0,0,-1,-1,1,1};
const int dy[9] = {0,0,0,-1,1,-1,1,-1,1};
const double pi = acos(-1.0);
const int N = 310;
int n;
LL a,b,f[N];
vector <int> v1,v2;
LL get_ans(LL ma)
{
int len = v1.size();
rep1(i,0,len-1)
f[i+1] = ma/v1[i];
rep2(i,len,1)
rep1(j,i+1,len)
if (v1[j-1]%v1[i-1]==0)
f[i]-=f[j];
return f[1];
}
int main()
{
//freopen("F:\\rush.txt","r",stdin);
ios::sync_with_stdio(false),cin.tie(0);//scanf,puts,printf not use
int T;
cin >> T;
rep1(ii,1,T)
{
v1.clear(),v2.clear();
cin >> a >> b >> n;
int len = sqrt(n);
rep1(i,1,len)
if (n%i==0)
{
int x = i,y = n/i;
v1.pb(x);
if (x!=y) v2.pb(y);
}
int len2 = v2.size();
rep2(i,len2-1,0) v1.pb(v2[i]);
LL t1 = get_ans(b),t2 = get_ans(a-1);
cout <<"Case #"<<ii<<": ";
cout << t1-t2<<endl;
}
return 0;
}
最新文章
- node fs lstat 如何区别文件和文件夹
- C++中重定义的问题——问题的实质是声明和定义的关系以及分离式编译的原理
- SqlLite 基本操作
- win10磁盘100%解决办法
- QStandardItemModel-Delegate
- 从自签名证书导出pfx和cer证书
- (剑指Offer)面试题32:从1到n整数中1出现的次数
- Codeforces Round #340 (Div. 2) C. Watering Flowers 暴力
- JS中escape 方法和C#中的对应
- perl 对象 通过bless实现
- phpcms2008常用函数小结
- TurnipBit口袋编程计算机:和孩子一起DIY许愿的流星
- Spring源码情操陶冶-任务定时器ConcurrentTaskScheduler
- Skyline 7 版本TerraExplorer Pro二次开发快速入门
- 设置光标聚焦输入框(EditText)并弹出软键盘(在适配器中设置)
- iOS 字体下载
- nginx新增tcp模板
- 腾讯AlloyTeam正式发布omi-cli脚手架 - 创建网站无需任何配置
- -webkit-line-clamp超出省略
- emouse思·;睿&mdash;评论与观点整理之一
热门文章
- HDU 5402 Travelling Salesman Problem (模拟 有规律)(左上角到右下角路径权值最大,输出路径)
- poj2135(简单的最小费用流问题)
- 零基础学python-2.16 列表解析
- apple 团队电话
- hdu1209(Clock)
- Unity 使用C/C++ 跨平台终极解决方式(PC,iOS,Android,以及支持C/C++的平台)
- nyoj--973--天下第一(SPFA判断负环)
- mysql 操作提示 1366 Incorrect string value
- (转载)activity外部调用startActivity的new task异常解析
- windows server 2008 R2开机进度条闪过后黑屏