Mail.Ru Cup 2018 Round 3 B. Divide Candies (数论)

Mail.Ru Cup 2018 Round 3 B. Divide Candies

• 题意：问有多少对\((i^2+j^2)\ 1\le i,j\le n\)能整除\(m\ (1\le m\le 1000)\)

• 题解：首先我们只用考虑\([0,m-1]\)，因为后面都是循环节，直接计算贡献即可。

  那么我们就有\(\lfloor \frac{n}{m} \rfloor\)个块，此外可能还剩下一个不完整的块。计算\([0,m-1]\)中\(i*i \mod m\)的个数，即\(mp[i*i\mod m]+=n/m\)，再计算\([n/m*m+1,n]\)的贡献，最后枚举\([0,m-1]\)直接计算答案，注意\(i=0\)时的特判.

• 代码：

  #include 
  #define ll long long
  #define fi first
  #define se second
  #define pb push_back
  #define me memset
  #define rep(a,b,c) for(int a=b;a<=c;++a)
  #define per(a,b,c) for(int a=b;a>=c;--a)
  const int N = 1e6 + 10;
  const int mod = 1e9 + 7;
  const int INF = 0x3f3f3f3f;
  using namespace std;
  typedef pair PII;
  typedef pair PLL;
  ll gcd(ll a,ll b) {return b?gcd(b,a%b):a;}
  ll lcm(ll a,ll b) {return a/gcd(a,b)*b;}
   
  ll n,m;
  unordered_map mp;
   
  int main() {
  	scanf("%lld %lld",&n,&m);
  	
  	for(int i=0;i