首页 > 代码库 > jzoj2700 【GDKOI2012模拟02.01】数字
jzoj2700 【GDKOI2012模拟02.01】数字
传送门:https://jzoj.net/senior/#main/show/2700
【题目大意】
令n为正整数,S(n)为n的各位数字之和,令
小Z喜欢的数一定能表示成 x * D(x) 这种形式。
小D也是个开朗的人,他知道QQ号码是随出来的。那么,他想知道在区间[L, R]中,他喜欢的数出现了多少次呢?
多组数据。
1<=T<=5, 1<=L<=R<=10^18
【题解】
打一个表就知道D(n)=((n-1) mod 9) + 1
然后我们如果有k * D(k) = n,那么有n + X = (k + X/D(k)) * D(k + X/D(k))。
由于D(k)属于1~9,2520为1~9的公倍数,且D(k)是9个一循环,所以X/D(k)也要是9的倍数,所以X最小值为2520 * 9。
早上不管这么多直接刚了个3628800就过了。。
# include <stdio.h> # include <string.h> # include <iostream> # include <algorithm> // # include <bits/stdc++.h> using namespace std; typedef long long ll; typedef long double ld; typedef unsigned long long ull; const int M = 5e5 + 10, F = 3628800; const int mod = 1e9+7; # define RG register # define ST static int T; ll L, R; bool ok[F + 5]; int all; inline int D(ll x) {return (x-1)%9+1;} # define beg(x) ((x-1)*F+1) # define end(x) (x*F) # define block(x) ((x-1)/F+1) # define ord(x) ((x-1)%F+1) inline void sol() { cin >> L >> R; ll le = block(L), ri = block(R), ans = 0; if(le == ri) { for (ll i=L; i<=R; ++i) ans += ok[ord(i)]; cout << ans << endl; return ; } if(ri - le >= 2) ans = (ll)(ri - le - 1) * all; for (ll i=end(le); i>=L; --i) ans += ok[ord(i)]; for (ll i=beg(ri); i<=R; ++i) ans += ok[ord(i)]; cout << ans << endl; } int main() { // freopen("num.in", "r", stdin); // freopen("num.out", "w", stdout); cin >> T; for (int i=1, t; i<=F; ++i) { for (int j=1; j<=9; ++j) { if(i%j) continue; t = i/j; if(D(t) == j) { ok[i] = 1; break; } } all += ok[i]; } while(T--) sol(); return 0; }
jzoj2700 【GDKOI2012模拟02.01】数字
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。