// Łukasz Proksa, Silesian University of Technology, Poland // Potyczki Algorytmiczne 2015, trial round // Task "Równanie" // Solved! O(30 000) #include <iostream> using namespace std; typedef long long LL; #define FOR(i, b, e) for(int i = (b); i <= (e); ++i) #define MIN(a, b) ((a) < (b) ? (a) : (b)) static const int MAX_SUM = 1458; bool isSum[1459]; LL a, b, k; int f(LL n) { int sum = 0; while (n > 0LL) { // O(18) int d = (int)(n % 10LL); sum += d*d; n /= 10LL; } return sum; } int main() { ios_base::sync_with_stdio(false); FOR(i, 0, MAX_SUM) { isSum[i] = true; } isSum[1350]=0;isSum[1355]=0;isSum[1363]=0;isSum[1365]=0;isSum[1366]=0; isSum[1367]=0;isSum[1371]=0;isSum[1372]=0;isSum[1374]=0;isSum[1380]=0; isSum[1382]=0;isSum[1383]=0;isSum[1384]=0;isSum[1387]=0;isSum[1388]=0; isSum[1389]=0;isSum[1391]=0;isSum[1395]=0;isSum[1397]=0;isSum[1398]=0; isSum[1399]=0;isSum[1400]=0;isSum[1401]=0;isSum[1403]=0;isSum[1404]=0; isSum[1405]=0;isSum[1406]=0;isSum[1408]=0;isSum[1410]=0;isSum[1411]=0; isSum[1412]=0;isSum[1414]=0;isSum[1415]=0;isSum[1416]=0;isSum[1417]=0; isSum[1418]=0;isSum[1419]=0;isSum[1420]=0;isSum[1421]=0;isSum[1422]=0; isSum[1423]=0;isSum[1425]=0;isSum[1427]=0;isSum[1428]=0;isSum[1429]=0; isSum[1430]=0;isSum[1431]=0;isSum[1432]=0;isSum[1433]=0;isSum[1434]=0; isSum[1435]=0;isSum[1436]=0;isSum[1437]=0;isSum[1438]=0;isSum[1439]=0; isSum[1440]=0;isSum[1442]=0;isSum[1443]=0;isSum[1444]=0;isSum[1445]=0; isSum[1446]=0;isSum[1447]=0;isSum[1448]=0;isSum[1449]=0;isSum[1450]=0; isSum[1451]=0;isSum[1452]=0;isSum[1453]=0;isSum[1454]=0;isSum[1455]=0; isSum[1456]=0;isSum[1457]=0; cin>>k>>a>>b; LL first = a/k + (LL)(a % k != 0); // ceil(a / k) if (first > (LL)MAX_SUM) { cout<<"O"<<endl; return 0; } int st = (int)first; int last = (int)MIN((LL)MAX_SUM, b/k); // floor(b / k) int cnt = 0; FOR(sum, st, last) { // for each 'sum', such that a <= k*sum <= b is satisfied if (!isSum[sum]) { continue; } LL n = k*(LL)sum; if (f(n) == sum) { cnt++; } } cout<<cnt<<endl; return 0; }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 | // Łukasz Proksa, Silesian University of Technology, Poland // Potyczki Algorytmiczne 2015, trial round // Task "Równanie" // Solved! O(30 000) #include <iostream> using namespace std; typedef long long LL; #define FOR(i, b, e) for(int i = (b); i <= (e); ++i) #define MIN(a, b) ((a) < (b) ? (a) : (b)) static const int MAX_SUM = 1458; bool isSum[1459]; LL a, b, k; int f(LL n) { int sum = 0; while (n > 0LL) { // O(18) int d = (int)(n % 10LL); sum += d*d; n /= 10LL; } return sum; } int main() { ios_base::sync_with_stdio(false); FOR(i, 0, MAX_SUM) { isSum[i] = true; } isSum[1350]=0;isSum[1355]=0;isSum[1363]=0;isSum[1365]=0;isSum[1366]=0; isSum[1367]=0;isSum[1371]=0;isSum[1372]=0;isSum[1374]=0;isSum[1380]=0; isSum[1382]=0;isSum[1383]=0;isSum[1384]=0;isSum[1387]=0;isSum[1388]=0; isSum[1389]=0;isSum[1391]=0;isSum[1395]=0;isSum[1397]=0;isSum[1398]=0; isSum[1399]=0;isSum[1400]=0;isSum[1401]=0;isSum[1403]=0;isSum[1404]=0; isSum[1405]=0;isSum[1406]=0;isSum[1408]=0;isSum[1410]=0;isSum[1411]=0; isSum[1412]=0;isSum[1414]=0;isSum[1415]=0;isSum[1416]=0;isSum[1417]=0; isSum[1418]=0;isSum[1419]=0;isSum[1420]=0;isSum[1421]=0;isSum[1422]=0; isSum[1423]=0;isSum[1425]=0;isSum[1427]=0;isSum[1428]=0;isSum[1429]=0; isSum[1430]=0;isSum[1431]=0;isSum[1432]=0;isSum[1433]=0;isSum[1434]=0; isSum[1435]=0;isSum[1436]=0;isSum[1437]=0;isSum[1438]=0;isSum[1439]=0; isSum[1440]=0;isSum[1442]=0;isSum[1443]=0;isSum[1444]=0;isSum[1445]=0; isSum[1446]=0;isSum[1447]=0;isSum[1448]=0;isSum[1449]=0;isSum[1450]=0; isSum[1451]=0;isSum[1452]=0;isSum[1453]=0;isSum[1454]=0;isSum[1455]=0; isSum[1456]=0;isSum[1457]=0; cin>>k>>a>>b; LL first = a/k + (LL)(a % k != 0); // ceil(a / k) if (first > (LL)MAX_SUM) { cout<<"O"<<endl; return 0; } int st = (int)first; int last = (int)MIN((LL)MAX_SUM, b/k); // floor(b / k) int cnt = 0; FOR(sum, st, last) { // for each 'sum', such that a <= k*sum <= b is satisfied if (!isSum[sum]) { continue; } LL n = k*(LL)sum; if (f(n) == sum) { cnt++; } } cout<<cnt<<endl; return 0; } |