首页 > 代码库 > 【CSU 1803】2016
【CSU 1803】2016
http://acm.csu.edu.cn/OnlineJudge/problem.php?id=1803
Solution:
考虑两个数x,y乘积%2016=0
x×y≡0(MOD 2016)
x=p1×2016+q1
y=p2×2016+q2
x×y=(p1×2016+q1)×(p2×2016+q2)=2016^2×p1p2+2016(p1q2+q1p2)+p1p2≡0(MOD 2016)
实际上就转化为余数乘积取模=0,预处理没两个余数乘积是否mod2016=0
统计答案两个余数出现的个数相乘即可(注意特判0不能选)
复杂度:O(2016^2)
// <1803.cpp> - Wed Oct 19 08:25:53 2016// This file is made by YJinpeng，created by XuYike‘s black technology automatically.// Copyright (C) 2016 ChangJun High School, Inc.// I don‘t know what this program is.#include <iostream>#include <vector>#include <algorithm>#include <cstring>#include <cstdio>#include <cstdlib>#include <cmath>#define MOD 2016#define src(x,n) (n/MOD+(x!=0?(n%MOD>=x):0))using namespace std;typedef long long LL;vector<pair<int,int> >a;int main(){ freopen("1803.in","r",stdin); freopen("1803.out","w",stdout); for(int i=0;i<MOD;i++) for(int j=0;j<MOD;j++) if((i*j)%MOD==0) a.push_back(make_pair(i,j)); int n,m,to=a.size(); while(~scanf("%d%d",&n,&m)){ LL ans=0; for(int i=0;i<to;i++) ans+=1LL*src(a[i].first,n)*src(a[i].second,m); printf("%lld\n",ans); } return 0;}
【CSU 1803】2016
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。