题意：输入T组数，每组有两个数，求出n-m区间内不含有7且不能被7整除且各个位数相加之和不被7整除的数的平方和。数据在1--1e18，结果对1e9+7。由于数太大，容易溢出，所以比较麻烦的是要把数拆开。
#include <iostream> #include <algorithm> #include <cstring> #include <cstdio> #include <math.h> #include <cstdlib> #include <vector> using namespace std; #define LL long long const int MOD = 1E9 + 7; struct Node { LL cnt;///符合条件的个数 LL sum;///符合条件数的和 sum LL sqsum;///平方和 Node(){} Node(LL a, LL b, LL c):cnt(a), sum(b), sqsum(c){} }dp[20][7][7]; int dis[20]; LL c[20]; Node dfs(int len, int pra, int prb, bool flag) { if(len < 0) { return Node(pra!=0 && prb!=0, 0, 0); } if(!flag && dp[len][pra][prb].cnt != -1) return dp[len][pra][prb]; int end = flag?dis[len]:9; Node ans = Node(0, 0, 0); for(int i=0; i<=end; i++) { if(i != 7) { ///假定dfs推出返回的结构体是ans，当前结果的结构体是t Node t = dfs(len-1, (pra+i)%7, (prb*10+i)%7, flag && i==end); ans.cnt = (ans.cnt + t.cnt) % MOD; ans.sum += (((c[len]*i)%MOD)*t.cnt%MOD + t.sum) % MOD;///其中(10^len*i)*t.cnt代表以i为首位的这部分数字和。 ans.sum %= MOD; ans.sqsum += (t.sqsum+ ((2*c[len]*i)%MOD*t.sum)%MOD) %MOD;///sqsum+=(2*10^len*i*x)*t.cnt=(2*10^len*i)*t.sum(神奇的化简） ans.sqsum %= MOD; ans.sqsum += ((i*c[len]*i%MOD)*c[len]%MOD * t.cnt) %MOD; ans.sqsum %= MOD; } } if(!flag) dp[len][pra][prb] = ans; return ans; } void init() { c[0] = 1; for(int i=1; i<20; i++) c[i] = (c[i-1]*10) % MOD; } LL solve(LL n) { int len = 0; while(n) { dis[len++] = n%10; n /= 10; } Node ans; ans = dfs(len-1, 0, 0, 1); return ans.sqsum; } int main() { int T; scanf("%d", &T); init(); memset(dp, -1, sizeof(dp)); while(T--) { LL l, r; scanf("%lld%lld", &l, &r); printf("%lld\n", (solve(r) - solve(l-1) + MOD) % MOD); } return 0; }